剑指 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 为正整数
做题思路：
首先看到这道题，会觉得很简单，因为觉得来一个for循环就可以了，其实如果简单来做是这样的，但就怕是按照大数来写代码，那么这个难度就不言而喻了。
一、简单的方法
class Solution {
public int[] printNumbers(int n) {
int[] res = new int[(int)Math.pow(10 , n) - 1];
for (int i = 0; i < res.length; i++) {
res[i] = i + 1;
}
return res;
}
}
二、大数打印解法
做题思路：
首先要解决三个问题，参考了leetcodeK神：
- 表示大数的变量类型：
无论是 short / int / long ... 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。 - 生成数字的字符串集：
使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 "9999" 至 "10000" 需要从个位到千位循环判断，进位 4 次。
观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。
- 递归生成全排列：
基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n = 2n=2 时（数字范围 1 - 991?99 ），固定十位为 00 - 99 ，按顺序依次开启递归，固定个位 00 - 99 ，终止递归并添加数字字符串。
class Solution {
int[] res;
int nine = 0, start, n,count = 0;
char[] num,loops = {‘0‘,‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘};
public int[] printNumbers(int n) {
this.n = n;
res = new int[(int)Math.pow(10, n) - 1];
num = new char[n];//定义长度为n
start = n - 1;
dfs(0);//开启全排列递归
return res;
}
void dfs(int x) {
/*
主要这倒题，要先了解一下递归生成全排列的思路。
首先要先固定高位，再向低位递归。
例如当n=3时（100-999）,固定百位为0-9，按顺序依次开启递归，固定十位0-9,固定个位0-9，然后
终止递归并添加到数字字符串
*/
if (x == n) {//终止条件：已固定完所有位置
String s = String.valueOf(num).substring(start);
if (!s.equals("0"))
res[count++] = Integer.parseInt(s);
if (n - start == nine) //当n=1时 start=0 当n=2时 start=1
start--;
return;
}
for(char i : loops) {//遍历0-9
if(i == ‘9‘) nine++; //等到9的时候，再递增到10
num[x] = i;//固定x位为i
dfs(x + 1);//并开启固定x+1位
}
nine--;//这里是为了在回溯前恢复nine
}
}