# 剑指Offer题解 - Day67
# 剑指 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]
1
2
2
说明：
- 用返回一个整数列表来代替打印
- n 为正整数
思路：
首先考虑使用暴力法求解。核心思路就是初始化10^n - 1 长度的空数组，并循环填充索引加1。
最终返回该数组即可。
# 暴力法
/**
* @param {number} n
* @return {number[]}
*/
var printNumbers = function(n) {
return Array.from({ length: Math.pow(10, n) - 1 }, (_, i) => i + 1);
};
1
2
3
4
5
6
7
2
3
4
5
6
7
- 时间复杂度 O(10^n)。
- 空间复杂度 O(1)。
分析：
不考虑数组与数字越界的情况下，直接循环10^n 次是最简单粗暴的办法。
但是实际上，本题的主要考点是大数越界情况下的打印。因此需要注意以下问题：
- 大数用number表示可能会超出数字的界定范围，因此使用字符串表示。
- 生成的最终结果是0~9的排列组合，可以通过递归生成最终结果。
- 基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。
- 需要删除高位多余的0，并且列表从1开始递增。
# 递归
/**
* @param {number} n
* @return {number[]}
*/
var printNumbers = function(n) {
let num = Array(n).fill('0');
let res = [];
let nine = 0; // 记录9出现的次数
let start = n - 1; // 记录字符串的左边界
const dfs = (x) => {
if (x === n) {
let s = num.slice(start).join('');
if (s !== '0') res.push(+s); // 跳过字符为0的情况
if (n - start === nine) start -= 1;
return;
}
for (let i = 0; i < 10; i++) {
if (i === 9) nine += 1;
num[x] = '' + i;
dfs(x + 1)
}
nine -= 1;
}
dfs(0);
return res
};
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
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
- 时间复杂度 O(10^n)。
- 空间复杂度 O(10^n)。
分析：
本方法是固定高位，然后从低位递归来达到统计的目的。
先来看正常递归时的逻辑。因为每一位都会出现0~9，因此这里需要遍历可能出现的数字。当遇见数字9时，统计9出现次数的nine变量遍历递增1。然后将当前位数字转换为字符串并放入当前位。然后递归高位。
当递归到最高位时，此时就需要终止递归。首先截取有效字符串。如果当前字符串不为'0' ，则转换为数字，并放入最终的结果数组中。如果遇到需要进位的情况，字符串的左边界就要左移一位。
当回溯的时候，需要将nine变量递减1，恢复原状。
最终返回结果数组即可。因为题目要求返回数字数组，所以在放入结果数组时，需要转换为数字。如果不要求返回数字，那么就不需要转换，可以表示出很大的数字字符串。
# 总结
递归生成的排列数量为10^n - 1 ，因此时间复杂度是O(10^n) ，结果数组占用O(10^n) 额外空间。