leetcode LexicographicalNumbers
z
 2019-04-09 10:36:27   
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);
    }
  }
}