剑指 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;//回溯 } }