386.字典序排数

链接：386.字典序排数
难度：Medium
标签：深度优先搜索、字典树
简介：给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

题解 1 - cpp

• 编辑时间：2022-03-21
• 执行用时：16ms
• 内存消耗：11.2MB
• 编程语言：cpp
• 解法介绍：dfs 遍历每一层。

class Solution {
   public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for (int i = 1; i <= 9; i++) dfs(ans, n, i);
        return ans;
    }
    void dfs(vector<int> &ans, int &max, int num) {
        if (num > max) return;
        ans.push_back(num);
        for (int i = 0; i <= 9; i++) dfs(ans, max, num * 10 + i);
    }
};

题解 2 - cpp

• 编辑时间：2022-04-18
• 执行用时：12ms
• 内存消耗：11.2MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for (int i = 1; i <= 9; i++) dfs(ans, n, i);
        return ans;
    }
    void dfs(vector<int> &ans, int &n, int num) {
        if (num > n) return;
        ans.push_back(num);
        for (int i = 0; i <= 9; i++) dfs(ans, n, num * 10 + i);
    }
};

题解 3 - cpp

• 编辑时间：2022-04-18
• 执行用时：8ms
• 内存消耗：10.2MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans(n);
        int num = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = num;
            if (num * 10 <= n)
                num *= 10;
            else {
                while (num % 10 == 9 || num + 1 > n) num /= 10;
                num++;
            }
        }
        return ans;
    }
};