Poison

剑指 Offer 17. 打印从1到最大的n位数

Simulation
1
2
3
4
5
6
7
8
9
class Solution {
public int[] printNumbers(int n) {
int[] res = new int[(int) Math.pow(10, n) - 1];
for (int i = 0; i < res.length; i++) {
res[i] = i + 1;
}
return res;
}
}
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private static final char[] NUMS = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

private static class State {
private int startIndex;
private int countOfNine;
private int resIndex;
private final int n;

public State(int n) {
this.n = n;
this.startIndex = n - 1; // 不要忘记初始化 startIndex, 且为最右侧元素索引,注意不是 0
}
}

public int[] printNumbers(int n) {
int[] res = new int[(int) Math.pow(10, n) - 1];
char[] numArray = new char[n];
State state = new State(n);
StringBuilder sb = new StringBuilder();
dfs(res, numArray, 0, state);
return res;
}

private void dfs(int[] res, char[] numArray, int level, State state) {
if (level == state.n) {
int value = Integer.parseInt(new String(numArray).substring(state.startIndex));
if (value != 0) {
res[state.resIndex++] = value;
}

if (state.countOfNine + state.startIndex == state.n) {
state.startIndex--;
}

return; // 此处不要忘记 return
}

for (char num : NUMS) {
if (num == '9') {
state.countOfNine++;
}

numArray[level] = num;
dfs(res, numArray, level + 1, state);
}

state.countOfNine--;
}
}
Reference

剑指 Offer 17. 打印从1到最大的n位数