[leetcode386]字典序排数

https://leetcode-cn.com/problems/lexicographical-numbers/submissions/

dfs

从每一位进行dfs 从1开始 注意第一位1-9 其余位置是0-9 枚举第一位进行dfs

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

迭代

直接进行n次 先尽量*10 如果大于n则进行 j++

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