努力刷题的钢铁桂桂卷(๑•̀ㅂ•́)و✧
大数打印题目描述
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
桂桂卷的率真解法
刚开始为秋招准备，这些题一看就只会暴力解除:
1
2
3
class Solution:
def printNumbers(self, n: int) -> List[int]:
return [i+1 for i in range(0, 10**n-1)]
（时间复杂度O(10n)，空间复杂读度O(1)）。虽然提交通过，但是面试的时候肯定不是考这种解题思路的( -‘`-; )
大神们的厉害解法
大神们总是能考虑得更多一些，比如这道大数打印题就需要考虑大数越界问题啦。
厉害得解法之一呢，就是使用字符串表示数字，并使用递归的思想。下面是大神的递归写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
具体的解题思路大家可以移步这里
写这份博客的目的是：给出递归解法的图示、简化高位零的删除过程，以便桂桂卷和大家都能更好地理解大数打印的递归解法。
桂桂卷给出n=2的情况，其他情况类似。
递归图示
（1）num[0]=0，num[1]=0,1,…,9
（2）num[0]=1，num[1]=0,1,…,9
（3）依此类推，当num[0]从0至9循环结束时，res数组生成完毕，此时res=[00, …, 09, 10,…19, …, 90, …, 99]，算法结束。
桂桂卷进击之路—简化高位零的删除过程
大神题解的高位删除算法使用了两个变量：nine、start。琢磨了一天，本桂酱还是没有理解透( ‘-ωก̀ )
于是就按着自己的想法，给出只使用start变量的解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def printNumbers(self, n: int) -> List[int]:
def dfs(x):
if x == n:
s = ''.join(num[self.start:])
if s != '0': res.append(int(s))
return
for i in range(10):
num[x] = str(i)
dfs(x+1)
if self.start>0: self.start -= 1
num, self.start, res = ['0']*n, n-1, []
dfs(0)
return res
解题思路：直观来看，几次for循环就意味着几次进位， 所以在每次for循环之后start变量减1就可以控制删除几个高位零了。但有一点值得注意的是，高位遍历的时候，个位会遍历多次，也就是说个位的一次完整for循环，有时候并不真正代表一次进位。这种时候只需要给start变量加一层判断：当start为零时便不再往下减就行了。(ฅ´ω`ฅ)
好啦，大数打印的递归图示以及高位删除过程的简化到这里就分析完毕咯。
桂桂卷祝大家吃到好吃的晚餐，明天依旧生活愉快嗷ψ(｀∇´)ψ
