剑指 Offer 17. 打印从1到最大的n位数
2021/4/12 10:58:01
本文主要是介绍剑指 Offer 17. 打印从1到最大的n位数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 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;//回溯 } }
这篇关于剑指 Offer 17. 打印从1到最大的n位数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!
- 2024-05-082024年,行业变动下的程序员应该首先学习哪种编程语言?