sixteen 、 Dictionary order number

16.1、 Question design requirements

   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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/lexicographical-numbers

16.2、 Their thinking

   First give cur take 1 To 9 The number above , And then in turn n Compare , If n Greater than or equal to cur Represents the number of , Will cur Add to res in , I'll use cur For ten , The number of hundreds is the same as n Compare , If less than or equal to n, Then continue to add res in , Finally, output .

16.3、 Algorithm

class Solution {
    
    List<Integer> res;

    public List<Integer> lexicalOrder(int n) {
    
        res = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
    
            dfs(i , n);
        }
        return res;
    }

    //cur Current bit 
    public void dfs(int cur,int n){
    
        // disqualification 
        if (cur > n){
    
            return;
        }
        // Add eligible to res in 
        res.add(cur);
        // Will be with cur For ten , Compare and add numbers such as hundreds 
        for (int i = 0; i <= 9; i++) {
    
            int nextNum = cur * 10 + i;
            if (nextNum > n){
    
                break;
            }
            // If nextNum Less than n, Do it again dfs
            dfs(nextNum,n);
        }
    }
}

Reference video ：B standing up Lord Guo wg