386. Lexicographical Numbers

发表于 | 分类于

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.

解法1： DFS

观察规律的话，其实是从每一个数字往下画一个树。对于X，下面的数字就是x*10 + i, i从0到9为止。
而X的范围是1到9。
这样的话就很容易写出来DFS的程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            helper(res, i, n);
        }
        return res;
    }
    private void helper(List<Integer> res, int current, int n) {
        if (current > n) {
            return;
        } else {
            res.add(current);
            for (int i = 0; i < 10; i++) {
                if (current * 10 + i > n) {
                    return;
                }
                helper(res, current * 10 + i, n);
            }
        }
    }
}

解法2： Ietration

也有iteration的做法，这个方法的核心就是对于每一个数字，要找出对应的下一个数字。
第二个和第三个if语句里面解决的是对于499下一个数字的问题，应该是5而不是500，所以这种情况下要把末尾的9去掉，然后再把结果+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int current = 1;
        for (int i = 1; i <= n; i++) {
            res.add(current);
            if (current * 10 <= n) {
                current *= 10;
            } else if (current % 10 != 9 && current + 1 <= n) {
                current++;
            } else {
                while ((current / 10) % 10 == 9) {
                    current /= 10;
                }
                current = current / 10 + 1;
            }
        }
        return res;
    }
}