剑指 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 为正整数

解题思路

大数打印问题。由题目可得，要打印的最大的数为10^num - 1。
这个题考验的是n很大的时候的大数越界问题，因为n可能>32，这时候int就没法表示了。
因此，要用string的方式表示int。本题返回的是int的list，实际上可能考察的是必须打印string的list。这就需要用排列组合的方式生成10^num - 1个string。
在python中，int转str的函数为str(int)，str转int的函数为int(str, base=n)，n为位数。
具体采用的算法为：
使用递归+分治算法的思想，每次递归dfs()仅仅使用for循环产生本进制为0-9的情况，一直递归到所有位数都能排列组合上“之前排列好的其他位数+本位数为0-9”的组合。

解题代码

class Solution:
    def printNumbers(self, n: int) -> list[int]:
        num_str_list = []
        # level:当前操作的位数.level为n的时候说明操作的是个位.num后面追加一个i
        def dfs(i, level: int, num_str: str):
            if level < n:
                for i in range(10):
                    if level == 1 and i == 0:  # 不需要01,02前面的0
                        dfs(i, level + 1, num_str)
                    else:
                        dfs(i, level + 1, num_str + str(i))
            elif level == n:
                for i in range(10):
                    # 其实这个题本意是打印,不需要转为int的
                    final_num_str = num_str + str(i)
                    num_str_list.append(int(final_num_str))
        dfs(0, 1, '')
        return num_str_list[1:]  # 不需要输出0,从1开始输出

执行结果

执行结果：通过
执行用时：64 ms, 在所有 Python3 提交中击败了20.88%的用户
内存消耗：21.2 MB, 在所有 Python3 提交中击败了5.01%的用户