剑指 Offer 17. 打印从 1 到最大的 n 位数
“对于程序员而言，刷了Leetcode不一定能拿offer，但是不刷肯定拿不到offer。”
剑指 Offer 17. 打印从 1 到最大的 n 位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
用返回一个整数列表来代替打印
n 为正整数
大数问题
简单来看，遍历计算即可获取答案，由于要求返回的是int[]，故不会出现溢出情况。
如果要求返回的是String，则是考察大数问题的处理。
$$
T(n) = O(10^n)
$$
$$
V(n) = O(10^n)
$$
String处理进位
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
| class Solution {
public int[] printNumbers(int n) {
int[] res = new int[(int)Math.pow(10, n) - 1];
StringBuilder str = new StringBuilder();
for (int i = 0; i < n; i++) {
str.append('0');
}
int count = 0;
while(!increment(str)) {
int index = 0;
while (index < str.length() && str.charAt(index) == '0'){
index++;
}
res[count++] = Integer.parseInt(str.toString().substring(index));
}
return res;
}
private boolean increment(StringBuilder str) {
boolean isCarry = false;
for (int i = str.length()-1; i >= 0; i--) {
char s = (char)(str.charAt(i) + 1);
if (s > '9') {
str.replace(i, i+1, "0");
if (i == 0) {
isCarry = true;
}
} else {
str.replace(i, i+1, String.valueOf(s));
break;
}
}
return isCarry;
}
}
|
dfs全排列
由于在09999这种情况下，会出现连续进位，遍历n-1次，需要从最低位到最高位循环判断，所以可以考虑全排列避开进位操作。（通过递归实现全排列，生成String列表）
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
| class Solution {
int[] res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'0','1','2','3','4','5','6','7','8','9'};
public int[] printNumbers(int n) {
this.n = n;
res = new int[(int)Math.pow(10,n)-1];
num = new char[n];
start = n - 1;
dfs(0);
return res;
}
private void dfs(int x) {
if (x == n) {
String s = String.valueOf(num).substring(start);
if (!s.equals("0")) res[count++] = Integer.parseInt(s);
if (n - start == nine) start--;
return;
}
for (char i : loop) {
if (i == '9') nine++;
num[x] = i;
dfs(x+1);
}
nine--;
}
}
|
