Leetcode(386) Lexicographical Numbers

发表于 | 分类于

Description

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.

解法

采用DFS的解法，其实就是十叉树的前序遍历嘛。参考二叉树的前序遍历即可

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        int root = 1;
        while (root <= n && root <= 9) {
            DFS(root, n);
            root += 1;
        }
        return result;
    }
    void DFS(int root,int n){
        result.add(root);
        for (int i = 0; i <= 9; i++) {
            if (root * 10 + i <= n) {
                DFS(root * 10 + i, n);
            }
        }
        return;
    }
}