【回溯-数字全排列&&dfs】LCR 135. 报数
实现一个十进制数字报数程序,请按照数字从小到大的顺序返回一个整数数列,该数列从数字 1
开始,到最大的正整数 cnt
位数字结束。
示例 1:
输入:cnt = 2 输出:[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]
cnt位数字的全排列,每个位取值范围【0-9】,故一共 Math.pow(10,cnt)个数字,由于从1开始所以要去掉0.
使用回溯依次从左向右设置数字,第i位数字取值【0,9】一直到设置到第cnt位,完成。
代码:
static class Solution{ public int k=0; public int[] countNumbers(int cnt) { int[] ans=new int[(int)Math.pow(10,cnt)-1]; dfs(0,cnt,0,ans); return ans; } public void dfs(int i,int cnt,int v,int[] ans){ if(i==cnt){ if(v>0) ans[k++]=v; //不含1 return; } for(int d=0;d<=9;d++){ dfs(i+1,cnt,v*10+d,ans); } } }
算法笔试题解-回溯系列 文章被收录于专栏
算法笔试题解-回溯系列