剑指 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位数实质是{0~9}在n位上的全排列，大数问题转字符串解决。
        固定前n-1位，第n位遍历{0~9}
        .
        .
        .
    需要考虑的问题：字符串首位为0的打印问题
    定义:start定位字符串的起始不为0的位置,
         nine当前位置遍历到9，需要向前进位，nine+=1
         if(n-start==nine)start--;向前进位
    *每次递归需要作nine-=1进行回溯
    leetcode这道题返回了int[]整型数组，解答实际上在最后又转了int，那么好的算法浪费了，记录下过程
**/
class Solution {
    char[] factors=new char[]{'0','1','2','3','4','5','6','7','8','9'};
    int start=0,nine=0,count=0;
    int[] allNums;//存储所有数，实际上应该是String类型较为合理
    char[] num;//存储每个数位，char[]很方便转String
    public int[] printNumbers(int n) {
        int len=(int)Math.pow(10,n)-1;//总数量
        allNums=new int[len];
        num=new char[n];
        start=n-1;//一开始定在最末尾
        dfs(0,n);
        return allNums;
    }
    public void dfs(int x,int n){
        if(x==n){
            String s=String.valueOf(num).substring(start);//从start开始截取
            if(!s.equals("0"))allNums[count++]=Integer.parseInt(s);//非0存入结果数组
            if(n-start==nine)start-=1;//进位
            return;//当前数位遍历完毕
        }
        for(char f:factors){
            if(f=='9')nine+=1;
            num[x]=f;//固定当前位
            dfs(x+1,n);//递归下一位
        }
        nine-=1;//回溯
    }
}