Title source

• LEETCODE

Title Description

title

Dictionary order , seeing the name of a thing one thinks of its function , It must be sorting strings in the order in the dictionary ： In fact, it is the size order of the first different characters from left to right , Whose first different character is smaller , Whose dictionary order is smaller . Take a few examples ：
（1）“013”<“12”, The first character is a different character ,‘0’<‘1’
（2）“21”<“23”, The second character is a different character ,‘1’<‘3’
（3）“3242432”<“32484343”, The fourth character is a different character ,‘2’<‘8’
Be careful ️, The dictionary order of a string has nothing to do with its length , Don't confuse .

The cross tree traverses first

Train of thought

0
|
-----------------------------------
|       |       |       | | | | | |
1       2       3       4 5 6 7 8 9
|       |       |       | | | | | |
10~19   20~29   30~39   ............

For input 20, The answer is ：

[1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9]

It can be seen that , It's actually the tree above The first sequence traversal DFS, Just put greater than 20 The number of （ also 0） Removed .

Train of thought two

take [1, n] All the numbers in the are sorted in dictionary order , It can be found that the numbers with the same prefix are clustered together . such as n=23, Output is [1,10,11,12,13,2,3,4,5,6,7,8,9], The prefix for 1 Of [1,10,11,12,13] Will gather together , In other words, it is actually a pre order traversal process of a cross tree

Train of thought three

take [1, n] The number of is added to the answer in dictionary order , In essence, the number of nodes is n, The form is similar to the multi-level tree of dictionary tree , The root node is 0, It needs to be skipped , So we can start searching from the second layer of the tree .

The value of each node in the tree is the number represented by its search path , And each node has [0, 9] common 10 Child node .

class Solution {
    
    // 1 , 10 , 11 , 12, 13
    void helper(int cur, int n, std::vector<int>& res){
    
        if(cur > n){
    
            return;
        }
        res.push_back(cur);
        for (int i = 0; i < 10; ++i) {
    
            helper(cur * 10 + i, n, res);
        }
    }
public:
    vector<int> lexicalOrder(int n) {
    
        std::vector<int> res;
        for (int i = 1; i < 10; ++i) {
    
            helper(i, n, res);
        }
        return res;
    }
};

Iterative writing

class Solution {
    
public:
    vector<int> lexicalOrder(int n) {
    
        // *10 Down , +1 towards the right 
        vector<int> ret(n);
        int number = 1;
        for (int i = 0; i < n; i++) {
    
            ret[i] = number;
            //  Normal down 
            if (number * 10 <= n) {
    
                number *= 10;  
            } else {
    
            	//  towards the right , Go back first 
                while (number % 10 == 9 || number == n) {
     // Reached the border 
                    number /= 10;  // upper story 
                }
                number++;
            }
        }
        return ret;
    }
};