05 August 2008
给一个整数，按照字典序排序
例子
1
2
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
DFS先序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res=new ArrayList<>();
// 没有0
for(int i=1;i<10;i++){
dfs(n,res,i);
}
return res;
}
void dfs(int n,List<Integer> res,int val){
if(val>n)return ;
res.add(val);
for(int j=0;j<=9;j++){
dfs(n,res,val*10+j);
}
}
}
从1开始, 一位一位的加到个位数的方式扩大数字, 这种方式先出现的满足n的数字 , 优先添加到ans中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
this.f(0, 1, n, ans);
return ans;
}
/**
* 以base为基数, 从start开始添加到个位数, <=n的结果添加到ans中
*
* @param base
* @param start
* @param n
* @param ans
*/
private void f(int base, int start, int n, List<Integer> ans) {
if (base > n)
return;
for (int i = start; i < 10; i++) {
int num = i + base;
if (num <= n) {
ans.add(num);
this.f(num * 10, 0, n, ans);
}
}
}
}