剑指 Offer 17. 打印从1到最大的n位数
2021/8/4 23:08:04
本文主要是介绍剑指 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 为正整数
做题思路:
首先看到这道题,会觉得很简单,因为觉得来一个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神:
- 表示大数的变量类型:
无论是 short / int / long ... 任意变量类型,数字的取值范围都是有限的。因此,大数的表示应用字符串 String 类型。 - 生成数字的字符串集:
使用 int 类型时,每轮可通过 +1+1 生成下个数字,而此方法无法应用至 String 类型。并且, String 类型的数字的进位操作效率较低,例如 "9999" 至 "10000" 需要从个位到千位循环判断,进位 4 次。
观察可知,生成的列表实际上是 nn 位 00 - 99 的 全排列 ,因此可避开进位操作,通过递归生成数字的 String 列表。
- 递归生成全排列:
基于分治算法的思想,先固定高位,向低位递归,当个位已被固定时,添加数字的字符串。例如当 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)
这篇关于剑指 Offer 17. 打印从1到最大的n位数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)