1竣稽、題目鏈接
https://leetcode.com/problems/lexicographical-numbers/
2氧秘、解題思路
題目意思大致是給你一個數(shù)字n，n最大是500W带膜，然后讓你給出一個列表瘫怜，有兩個條件：
- a、列表中的數(shù)必須不大于n
- b藕届、列表中的數(shù)字需要按照字典序排列
首先我們來說說字典序這個概念挪蹭，一般在字符串中用的比較多，字典序是說一個字符串中的字符從左到右依次增大休偶，一般來說是從左往右挨個比較梁厉，舉個例子，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]
有沒有發(fā)現(xiàn)什么，我們只需要計算從1-9的倍數(shù)（10的次方）饮醇，然后再加上0-9它抱，那么我們怎么讓它按照字典序來計算呢？不知道各位有沒有發(fā)現(xiàn)朴艰，從 1观蓄，10混移，100，101 ... 11一下子就回退到了從11開始侮穿，那么毫無疑問歌径，我們用遞歸來處理這樣一個問題；試想一下亲茅，當我們遞歸的時候從1到10再到100都把數(shù)字加到列表中回铛，然后到1000的時候我們需要終止該次的遞歸并退回到100的那一次遞歸，然后我們需要把101克锣，102...,109加入到列表茵肃，這時候我們需要給當次遞歸的數(shù)+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) { //當次遞歸的結(jié)束條件
return;
}
result.add(count); //把滿足條件的加入到列表中
int total = count * 10;
for (int i = 0; i < 10; i++) {
//total+i很關(guān)鍵
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验残、提交結(jié)果
ELiwCR.png
