剑指 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神：

1. 表示大数的变量类型：
   无论是 short / int / long ... 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。
2. 生成数字的字符串集：
   使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 "9999" 至 "10000" 需要从个位到千位循环判断，进位 4 次。

观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。

3. 递归生成全排列：
   基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 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
        }
    }

参考链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/（作者：jyd）