2024/09/21 Leetcode Daily Problem

386. Lexicographical Numbers
難度: 中等

題意

給定一整數n，回傳一整數陣列，值為1~n按照字典序(lexicographical)排列。

思路

題目直接說明要O(N)算法，因此自己寫字點序比較來排序應該是不能過。
我們要直接按照順序來產生，仔細觀察如下:

1 -> 10 -> 100 ...
        -> 101
        -> 102
        -> 103
        -> ...
        -> 109
  -> 11 -> 110
        -> 111
        -> 112
        -> ...
  -> 12 -> 120
        -> 121
        ...
  ...
  -> 19 -> 190
        -> 191
  ...
2 -> 20 -> 200 ...
        -> 201
        ...

是不是很像DFS~~

因此按照9~1的順需塞入堆疊中，這樣就可以從1先拿出來。
找出他的小孩，也就是乘十，再加9~1塞入堆疊中。
依此類推

實作

先做了兩版brute force生成的方法，結果都有順序錯誤，領了WA。
仔細觀察後決定用堆疊來存發生順序，避免出錯。

class Solution
{
public:
    vector<int> lexicalOrder(int n)
    {
        vector<int> res;
        if (n <= 0)
            return res;

        stack<int> st;
        for (int i = 9; i >= 1; i--)
            st.push(i);

        // DFS
        while (!st.empty())
        {
            int curr = st.top();
            st.pop();
            if (curr <= n)
                res.push_back(curr);

            curr *= 10;
            if (curr <= n)
            {
                // Add new children
                for (int i = 9; i >= 0; i--)
                    if ((curr + i) <= n)
                        st.push(curr + i);
            }
        }
        return res;
    }
};

分析

時間複雜度: O(N)，DFS
空間複雜度: O(N)，stack所需，但好像最多放logN?

總結