Leetcode 386. Number of dictionary rows

386、 Dictionary order number

1） Title Description

Give you an integer n , Returns the range in dictionary order [1, n] All integers in .

You have to design a time complexity of O(n) And the use of O(1) Extra space algorithm .

Example 1：

 Input ：n = 13
 Output ：[1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2：

 Input ：n = 2
 Output ：[1,2]

Tips ：

• 1 <= n <= 5 * 10^4

2） analysis

Depth-first search .

• start from 1 Start , Add a zero after , if start*10<=n, shows start*10 Is the next number . continue ;
• if start*10>n, So if start%10==9 perhaps start+1>n, Indicates that the current bit search is complete , Returns the previous digit plus one .

3）C++ Code

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