Skip to main content

386.字典序排数

caution

原题链接：https://leetcode-cn.com/problems/lexicographical-numbers/

思路​

递归：

  • 从样例中可以发现规律，开头的数字只有 1 到 9 开始，所以可以每次遍历第一个数，然后判断需不需要在以这个开头的数后面添加新的数。
  • 递归只需要执行添加数的操作即可。

代码​

递归：

class Solution {
public:
    vector<int> res;

    void dfs(int u, int n) {
        if (u > n) return ;
        res.push_back(u);
        for (int i = 0; i <= 9; i++) {
            dfs(u * 10 + i, n);
        }
    }
    vector<int> lexicalOrder(int n) {
        for (int i = 1; i <= 9; i++) dfs(i, n);
        return res;
    }
};

迭代：

class Solution {
public:
    vector<int> res;

    vector<int> lexicalOrder(int n) {
        for (int i = 0, j = 1; i < n; i++) {
            res.push_back(j);
            if (j * 10 <= n) {
                j *= 10;
            } else {
                while (j % 10 == 9 || j + 1 > n) j /= 10;
                j++;
            }
        }
        return res;
    }
};