。字典數字

386。字典數字

難度：中

主題：深度優先搜索，Trie

給定一個整數 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 開始，每個節點最多有 9 個子節點，這些子節點由附加數字（0 到 9）組成。
• 我們可以透過從 1 開始並重複附加數字來模擬這種前序遍歷，確保我們不會超過給定的 n。

方法：

1. 從數字 1 開始，並嘗試透過乘以 10 來深入（即下一個字典數字與下一個數字）。
2. 如果不可能更深入（乘以 10）（即超過 n），請增加數字，確保它不會引入跨越十的無效跳躍（即從 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]

時間複雜度：

• O(n)，因為從 1 到 n 的每個數字都只處理一次。

空間複雜度：

• 使用了 O(1) 額外空間（忽略結果陣列所使用的空間）。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。字典數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！