LeetCode386. Lexicographical Num

1、题目链接

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

2、解题思路

题目意思大致是给你一个数字n，n最大是500W，然后让你给出一个列表，有两个条件：

• a、列表中的数必须不大于n
• b、列表中的数字需要按照字典序排列

首先我们来说说字典序这个概念，一般在字符串中用的比较多，字典序是说一个字符串中的字符从左到右依次增大，一般来说是从左往右挨个比较，举个例子，1 < 2，11 < 2，101 < 11......不知道大家有没有看懂，从左往右依次比较，相等的就比较下一位。所以，首先我们很容易想到的就是借助Collections的sort方法，因为这个方法对字符串就是默认按照字典序排列的；这种方法比较简单，就不再过多的介绍了；看看第二种方法，来看一下给的示例：

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

n = 130
result = [1,10,100,101,102,...,11,110,111,...,99]

有没有发现什么，我们只需要计算从1-9的倍数（10的次方），然后再加上0-9，那么我们怎么让它按照字典序来计算呢？不知道各位有没有发现，从 1，10，100，101 ... 11一下子就回退到了从11开始，那么毫无疑问，我们用递归来处理这样一个问题；试想一下，当我们递归的时候从1到10再到100都把数字加到列表中，然后到1000的时候我们需要终止该次的递归并退回到100的那一次递归，然后我们需要把101，102...,109加入到列表，这时候我们需要给当次递归的数+1，+2...+9

3、代码

• Java

public List<Integer> lexicalOrder(int n) {
    List<Integer> result = new ArrayList<>();
    for (int i = 1; i < 10; i++) {
        recursionLexicalOrder(i, n, result);
    }
    return result;
}
public void recursionLexicalOrder(int count, int n, List<Integer> result) {
    if (count > n) {  //当次递归的结束条件
        return;
    }
    result.add(count);  //把满足条件的加入到列表中
    int total = count * 10;
    for (int i = 0; i < 10; i++) {
        //total+i很关键
        recursionLexicalOrder(total + i, n, result);
    }
}

• Python

def lexicalOrder(n):
    result_list = []
    for index in range(1, 10):
        recursionLexicalOrder(index, n, result_list)
    return result_list


def recursionLexicalOrder(count, n, result_list):
    if count > n:
        return
    result_list.append(count)
    total = count * 10
    for index in range(0, 10):
        recursionLexicalOrder(total + index, n, result_list)

• JavaScript

var lexicalOrder = function(n) {
    let result_list = new Array()
    for (let i = 1; i < 10; i++) {
        this.recursionLexicalOrder(i, n, result_list)
    }
    return result_list
};

var recursionLexicalOrder = function(count, n, result_list) {
    if (count > n) {
        return
     }
     result_list.push(count)
     let total = count * 10
     for (let i = 0; i < 10; i++) {
         this.recursionLexicalOrder(total + i, n, result_list)
     }
};

4、提交结果