leetcode LexicographicalNumbers
z
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
29
30
31
32
33
34
35
36
37
import java.util.LinkedList;
import java.util.List;

public class LexicographicalNumbers {
/**
* Given an integer n, return 1 - n in lexicographical order.
*
* For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
*
* Please optimize your algorithm to use less time and space.
* The input size may be as large as 5,000,000.
*
* @param n
* @return
*/
public static List<Integer> lexicalOrder(int n) {
List<Integer> res = new LinkedList<Integer>();
for (int i=1; i<10; i++){
dfs(res, n, i);
}
return res;
}

public static void dfs(List<Integer> res, int n, int cur){
if (cur > n) return ;
res.add(cur);
for (int i=cur*10; i<cur*10+10; i++){
dfs(res, n, i);
}
return ;
}
public static void main(String[] args){
for (int c: lexicalOrder(19)){
System.out.println(c);
}
}
}