大数越界问题

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

示例

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

说明

• 用返回一个整数列表来代替打印
• n 为正整数

场景一：不考虑大数

题目要求打印 “从 1 至最大的 n 位数的列表” ，因此需考虑以下两个问题：

• 最大的 n 位数（记为 end ）和位数 n 的关系： 例如最大的 1 位数是 9 ，最大的 2 位数是 99 ，最大的 3 位数是 999 。则可推出公式：end=10的n ?1
• 大数越界问题： 当 n 较大时，end 会超出 int32 整型的取值范围，超出取值范围的数字无法正常存储。但由于本题要求返回 int 类型数组，相当于默认所有数字都存在 int32 整型取值范围内，因此不考虑大数越界问题。

因此，只需定义区间 [1,10的n方 ?1] 和步长 1 ，通过 for 循环生成结果列表 res 并返回即可。

代码如下：

复杂度分析

• 时间复杂度 ：O(10 的n次方 ) ，生成长度为 10的n次方 的列表需使用 O(10的n次方) 时间。
• 空间复杂度： O(1) ，建立列表需要使用 O(1) 大小的额外空间（ 列表作为返回结果，不计入额外空间 ）。

场景二：大数打印解法

实际上，本题的主要考点是大数越界情况下的打印。需要解决以下三个问题：

• 1. 表示大数的变量类型：无论是 short / int / long ... 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。

• 2. 生成数字的字符串集：使用 int 类型时，每轮可通过 +1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 "9999" 至 "10000" 需要从个位到千位循环判断，进位 4 次。
• 观察可知，生成的列表实际上是 n 位 0 - 9 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。
• 3. 递归生成全排列：基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n=2 时（数字范围 1?99 ），固定十位为 0 - 9 ，按顺序依次开启递归，固定个位 0 - 9 ，终止递归并添加数字字符串。

代码如下：

复杂度分析

• 时间复杂度：O(10的n次方) ，递归的生成的排列的数量为 10的n次方。
• 空间复杂度 ： O(10的n次方) ，结果列表 res 的长度为 10的n次方 ?1 ，各数字字符串的长度区间为 1,2,...,n ，因此占用 O(10的n次方 ) 大小的额外空间。

END

本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。