剑指Offer题解 - Day67

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

力扣题目链接[1]

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

「示例 1:」

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

• 用返回一个整数列表来代替打印
• 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);
};

• 时间复杂度 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
};

• 时间复杂度 O(10^n)。
• 空间复杂度 O(10^n)。

分析：

本方法是固定高位，然后从低位递归来达到统计的目的。

先来看正常递归时的逻辑。因为每一位都会出现0~9，因此这里需要遍历可能出现的数字。当遇见数字9时，统计9出现次数的nine变量遍历递增1。然后将当前位数字转换为字符串并放入当前位。然后递归高位。

当递归到最高位时，此时就需要终止递归。首先截取有效字符串。如果当前字符串不为'0'，则转换为数字，并放入最终的结果数组中。如果遇到需要进位的情况，字符串的左边界就要左移一位。

当回溯的时候，需要将nine变量递减1，恢复原状。

最终返回结果数组即可。因为题目要求返回数字数组，所以在放入结果数组时，需要转换为数字。如果不要求返回数字，那么就不需要转换，可以表示出很大的数字字符串。

总结

递归生成的排列数量为10^n - 1，因此时间复杂度是O(10^n)，结果数组占用O(10^n)额外空间。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/594wfg/