LeetCode 386. 字典序排数

1.题目

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

2.题解

这道题目是让我们对于任意一个小于5000000的整数给出一个从1到n的字典序排列的List集合。
那么关键就是什么是字典序？字典序有两个基本标准：ASCII码序和字符串长度；优先级：ASCII码序>字符串长度。
举个例子：如果n是134的话，我们应该怎么排列？
大致为[1,10,100,101,...,109,11,110,...,134,2,20,21,....]之后自然还有，但是大致如此。我之前理解为长度优先，写了半天，都是错的，所以审题很关键。
那么，我们应该怎么去思考这样的字典序呢？
首先，按照这样1到9的排列，我们基本可以以1-9（首位）和0到9作为循环的标准。
其次是理清楚下一位和上一位数之间的关系；
关系一：上一位数加1；例如：100到101；
关系二：上一位数*10；例如：10到100；
关系三：（上一位数加1）/10；例如：109到11；
三种关系判断的关键就是和n的比较，只要小于n,基本就可以添加到结果List中去。至于10倍递进到下一位的操作实质上都是一回事，只需要抽出一个判断10倍之后使用0到9循环判断的方法即可。

3.代码

Java

class Solution {
   public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 9; i++) {
            if (i > n) { break; }
            ttprocess(i, result, n);
        }          
        return result;
    }
    
    private void ttprocess(int i, List<Integer> result, int n) {
        result.add(i);
        for (int m = 0; m <= 9; m++) {
            if (i * 10 + m > n) {break;}
            ttprocess(i * 10 + m, result, n);
        }
    }
        
}

4.通过截图

image.png