。辞書編集上の番号

386。辞書編集番号

難易度: 中

トピック: 深さ優先検索、トライ

整数 n を指定すると、[1, n] の範囲内のすべての数値を辞書順にソートして返します。

O(n) 時間で実行され、O(1) 個の追加スペースを使用するアルゴリズムを作成する必要があります。

例 1:

• 入力: n = 13
• 出力: [1,10,11,12,13,2,3,4,5,6,7,8,9]

例 2:

• 入力: n = 2
• 出力: 4
• 説明: [1,2]

制約:

• 1 4

解決策:

深さ優先検索 (DFS) のような戦略を使用してアプローチできます。

主要な洞察:

• 辞書編集的な順序は、本質的には仮想 n 分ツリーにわたる前順序の走査であり、ルート ノードは 1 から始まり、各ノードには数字 (0 から 9) を追加することによって形成される最大 9 つの子があります。
• 1 から始めて数値を繰り返し追加し、指定された n を超えないようにすることで、この事前順序の走査をシミュレートできます。

アプローチ：

1. 数字 1 から始めて、10 (つまり、次の辞書編集上の数字と次の桁) を掛けてさらに深くしていきます。
2. さらに深くする (10 を掛ける) ことができない (つまり、n を超える) 場合は、10 の位をまたぐ無効なジャンプ (つまり、19 から 20 へ) が発生しないように、数値を増分します。
3. 現在の番号をこれ以上拡張できない場合はバックトラックし、次の有効な番号に移動します。
4. n までのすべての数値が処理されるまで続行します。

このソリューションを PHP で実装してみましょう: 386。辞書編集番号

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function lexicalOrder($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 13;
print_r(lexicalOrder($n1));

$n2 = 2;
print_r(lexicalOrder($n2));
?>

説明：

• 現在の番号を維持し、次の辞書編集番号を取得するために 10 を掛けて、できるだけ深く調べます。
• 掛け算ができない場合(nを超えてしまうため)、数値をインクリメントします。増分が 20、30 などの数値になる場合は、末尾のゼロをチェックし、それに応じて現在の数値を調整することで処理します。
• ループは、n までのすべての数値を辞書順に加算し終わるまで続きます。

チュートリアルの例:

入力: n = 13

1. 1 から始めます。
2. 1を10で掛ける -> 10.
3. 11、12、13 を追加します。
4. 2 に戻り、9 まで増加し続けます。

出力：

[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

入力: n = 2

1. 1 から始めます。
2. 2 に移動します。

出力：

[1, 2]

時間計算量:

• 1 から n までの各数値が 1 回だけ処理されるため、O(n)。

空間の複雑さ:

• O(1) 余分なスペースが使用されます (結果の配列に使用されるスペースは無視されます)。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。辞書編集上の番号の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。