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

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

❤❤❤大数打印解法——递归分治

思路

不管是任何数字类型，short,long,int均有表示范围，故大数打印仅能通过String实现。

  • 生成字符串，显然对于n位数，打印所有数即为0-9的全排列

    算法-递归

  • 基于分治思想，先固定高位，在固定低位，当个位被固定时，添加数字的字符串。

    1. def printNumbers(self,n:int) -> [int]:
    2.   def dfs(x):
    3.       if(x==n):
    4.           res.append(''.join(num))
    5.       for i in range(10):
    6.           num[x] =str(i)
    7.           def(x+1)    
    8.   num = ['0']*n
    9.   res=[]
    10.   dfs(0)
    11.   return ','.join(res)
    12. # 缺点
    13. # 高位0未删除
    14. # 次方法从0开始

  • 解决方法

    • 删除高位0
      • 定义左边界start，以保证num[start:]中无高位多余的0。例如n=2时，1-9时，start=1;10-99时，start=0，显然当当前位数全为9时，start需要往前进一位（0是高位），即减一
      • 假设当前num中9的个数为nine,则当start==n-nine时，start--
    • 删除初始数0，仅需在传入数组前加一个判断即可。
  1. class Solution:
  2.     def printNumbers(self, n: int) -> [int]:
  3.         def dfs(x):
  4.             if x == n:
  5.                 s = ''.join(num[self.start:])
  6.                 if s != '0': res.append(s)
  7.                 if n - self.start == self.nine: self.start -= 1
  8.                 return
  9.             for i in range(10):
  10.                 if i == 9: self.nine += 1
  11.                 num[x] = str(i)
  12.                 dfs(x + 1)
  13.             self.nine -= 1
  15.         num, res = ['0'] * n, []
  16.         self.nine = 0
  17.         self.start = n - 1
  18.         dfs(0)
  19.         return ','.join(res)

复杂度分析

  • 时间复杂度:17- ☆☆☆大数打印 - 图1
  • 空间复杂度:17- ☆☆☆大数打印 - 图2