Poison

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;
}
}
Reference

386. Lexicographical Numbers