leetcode 剑指offer 17. 打印从1 到n的最大n位数 （大数打印）

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

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

说明：用返回一个整数列表来代替打印，n 为正整数。

思路1： 暴力遍历一遍

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        for i in range(1, pow(10, n)):
            res.append(i)
        return res

这样存在的一个问题就是当数超过内置的最大值的时候就无法进行打印了，故本题考察的是大数打印。
思路2： 分治
即数一共是N位，每一位都可以是0-9，依次确定每一位即可；
但是仍需要注意：
1）会存在前几位为0的情况，如何去掉前几位的0
2）整体是从1开始输出的
参考的题解链接
采用string类型进行数值的保存，然后每次保存nums[start:]进行，来去掉前面的0，
start的确定方法是：n-self.nine; self.nine是数中9的个数，比如当00009,00099，00999这样的数出现之后，start需要往前移动一位。
具体详见代码：

class Solution:
    def printNumbers2(self, n: int):
        # 考虑大数的打印：即使用int long等存储不下的时候只能使用string进行
        def print_shu(l):
            if l == n:
                s = ''.join(nums[self.start:])
                if s != '0':
                    res.append(s)
                if n - self.start == self.nine:
                    self.start -= 1
                return
            for i in range(10):
                if i == 9:
                    self.nine += 1
                nums[l] = str(i)
                print_shu(l+1)
            self.nine -= 1

        res = []
        nums = ['0']*n
        self.nine, self.start = 0, n-1
        print_shu(0)
        return ''.join(res)

因为本题要求返回的是一个数组，为了可以通过，所以把每次得到的数转换成int然后直接返回res即可。（只是为了运行通过）

class Solution:
    def printNumbers(self, n: int) -> [int]:
        def dfs(x):
            if x == n:
                s = ''.join(num[self.start:])
                if s != '0': res.append(int(s))
                if n - self.start == self.nine: self.start -= 1
                return
            for i in range(10):
                if i == 9: self.nine += 1
                num[x] = str(i)
                dfs(x + 1)
            self.nine -= 1
        
        num, res = ['0'] * n, []
        self.nine = 0
        self.start = n - 1
        dfs(0)
        return res

最后

以上就是无心汽车为你收集整理的leetcode 剑指offer 17. 打印从1 到n的最大n位数 （大数打印）的全部内容，希望文章能够帮你解决leetcode 剑指offer 17. 打印从1 到n的最大n位数 （大数打印）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。