386. Lexicographical Numbers

, ,

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>(n);

        for (int i = 1; i <= 9; i++) {
            dfs(n, i, list);
        }

        return list;
    }

    private void dfs(int n, int i, List<Integer> list) {
        if (i > n) {
            return;
        }

        list.add(i);
        for (int j = 0; j <= 9; j++) {
            dfs(n, i * 10 + j, list);
        }
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>(n);

        int x = 1;
        while (list.size() < n) {
            // 进入至最下一层，在此过程中不断添加至结果集
            while (x <= n) {
                list.add(x);
                x *= 10;
            }

            // 此时 x 已经大于 n, 我们需要返回至上一层，如 190 需要返回到 19, 此时应该优先遍历 2, 所以我们使用了 while 探测尾部数字是否为 9, 此时应继续返回至 1 节点，以便进入到 2 节点
            while (x > n || x % 10 == 9) {
                x /= 10;
            }

            x++; // 移动至当前层的右侧节点
        }

        return list;
    }
}

References

386. Lexicographical Numbers