Sword to Offer | 面试题 14:打印从 1 到最大的 n 位数
死磕算法系列文章
- 干货 | 手撕十大经典排序算法
- 剑指offer | 认识面试
- 剑指offer | 面试题2:实现Singleton模式
- 剑指offer | 面试题3:二维数组的查找
- 剑指offer | 面试题4:替换空格
- 剑指offer | 面试题5:从尾到头打印链表
- 剑指offer | 面试题6:重建二叉树
- 剑指offer | 面试题7:用两个栈实现队列
- 剑指offer | 面试题8:旋转数组的最小数字
- 剑指offer | 面试题9:斐波那契数列
- 剑指offer | 面试题10:青蛙跳台阶问题
- 剑指offer | 面试题11:矩阵覆盖
- 剑指offer | 面试题12:二进制中1的个数
- 剑指offer | 面试题13:数值的整数次方
打印从1到最大的n位数
“Leetcode : https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof
“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_12_hammingWeight/Solution.java
题目描述: 输入数字 n
,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明:
- 用返回一个整数列表来代替打印
- n 为正整数
解题思路:
题目要求打印 “从 1 至最大的 n 位数的列表” ,因此需考虑以下两个问题:
- 最大的n位数(记为end)和位数n的关系: 例如最大的1位数是9,最大的2位数是99,最大的3位数是999。则可推出公式:
- 大数越界问题: 当n较大时,end会超出int32整型的取值范围,超出取值范围的数字无法正常存储。但由于本题要求返回int类型数组,相当于默认所有数字都在int32 整型取值范围内,因此不考虑大数越界问题。
因此,只需定义区间[1, 10”- 1]和步长1 ,通过for循环生成结果列表res并返回即可。复杂度分析:
- 时间复杂度 o(10^n) :生成长度为 10^n 的列表需使用 o(10^n) 时间。
- 空间复杂度 o(1) :建立列表需使用 o(1) 大小的额外空间(列表作为返回结果,不计入额外空间
代码:
package com.nateshao.sword_offer.topic_14_printNumbers;
import java.util.Arrays;
/**
* @date Created by 邵桐杰 on 2021/11/21 16:22
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
*/
public class Solution {
public int[] printNumbers(int n) {
int end = (int) Math.pow(10, n) - 1;
int[] res = new int[end];
for (int i = 0; i < end; i++)
res[i] = i + 1;
return res;
}
}
大数打印解法:
实际上,本题的主要考点是大数越界情况下的打印。需要解决以下三个问题:
- 表示大数的变量类型:
- 无论是short/ int/long ... 任意变类型,数字的取值范围都是有限的。因此,大数的表示应用字符串String类型。
- 生成数字的字符串集:
- 使用int类型时,每轮可通过+1生成下个数字,而此方法无法应用至String类型。并且,String类型的数字的进位操作效率较低,例如9999” 至“ 10000” 需要从个位到千位循环判断, 进位4次。
- 观察可知,生成的列表实际上是n位0-9的全排列,因此可避开进位操作,通过递归生成数字的String列表。
- 递归生成全排列:
- 基于分治算法的思想,先固定高位,向低位递归,当个位已被固定时,添加数字的字符串。例如当n=2时(数字范围1-99),固定十位为0-9 ,按顺序依次开启递归,固定个位0-9 ,终止递归并添加数字字符串。
class Solution {
StringBuilder res;
int count = 0, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public String printNumbers(int n) {
this.n = n;
res = new StringBuilder(); // 数字字符串集
num = new char[n]; // 定义长度为 n 的字符列表
dfs(0); // 开启全排列递归
res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
return res.toString(); // 转化为字符串并返回
}
void dfs(int x) {
if(x == n) { // 终止条件:已固定完所有位
res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部,使用逗号隔开
return;
}
for(char i : loop) { // 遍历 ‘0‘ - ’9‘
num[x] = i; // 固定第 x 位为 i
dfs(x + 1); // 开启固定第 x + 1 位
}
}
}
在此方法下,各数字字符串被逗号隔开,共同组成长字符串。返回的数字集字符串如下所示:
输入:n = 1
输出:"0,1,2,3,4,5,6,7,8,9"
输入:n = 2
输出:"00,01,02,...,10,11,12,...,97,98,99"
输入:n = 3
输出:"000,001,002,...,100,101,102,...,997,998,999"
观察可知,当前的生成方法仍有以下问题: .
- 诸如00, 01, 02,...应显示为0,1,2,...,即应删除高位多余的0 ;
- 此方法从0开始生成,而题目要求列表从1开始;
以上两个问题的解决方法如下:
- 删除高位多余的0 :
- 字符串左边界定义:声变量start规定字符串的左边界,以保证添加的数字字符串num[start:] 中无高位多余的0。 例如当n=2时,1-9时start=1,10- 99时start= 0。
- 左边界start变化规律: 观察可知,当输出数字的所有位都是9时,则下个数字需要向更高位进1,此时左边界start需要减1 (即高位多余的 0减少一个)。 例如当n=3 (数字范围1-999) 时,左边界start 需要减1的情况有: "009" 进位至"010","099" 进位至"100"。设数字各位中9的数量为nine,所有位都为9的判断条件可用以下公式表示:
- 统计nine的方法: 固定第x位时,当i=9则执行nine = nine +1,并在回溯前恢复nine = nine一1。
- 列表从1开始:
- 在以上方法的基础上,添加数字字符串前判断其是否为
"0"
,若为"0"
则直接跳过。
复杂度分析:
- 时间复杂度0(10^n) :递归的生成的排列的数量为10^n 。
- 空间复杂度0(10^n) :结果列表res的长度为10^n - 1,各数字字符串的长度区间为1.,....n, 因此占用O(10^n) 大小的额外空间。
代码:为正确表示大数,以下代码的返回值为数字字符串集拼接而成的长字符串。
class Solution {
int[] res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'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];
start = n - 1;
dfs(0);
return res;
}
void dfs(int x) {
if(x == n) {
String s = String.valueOf(num).substring(start);
if(!s.equals("0")) res[count++] = Integer.parseInt(s);
if(n - start == nine) start--;
return;
}
for(char i : loop) {
if(i == '9') nine++;
num[x] = i;
dfs(x + 1);
}
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
革命尚未成功,同志仍需努力,冲冲冲
推荐阅读
-
我的第一份年终总结 | 2021 年总结
-
计算机视觉应用 29-卷积神经网络(CNN)的变体:分组卷积、转置卷积和空卷积的计算过程-IV。空卷积简述
-
读完世界三大奇观,你就看到了地球的真相
-
安卓学习路线指南--分享一波入门面试题
-
向过去学习的 JavaScript - 绑定方法的实现
-
JavaScript 向过去学习--执行上下文和执行堆栈的机制
-
[webrtc] MessageHandler 1:基于线程的消息处理:10 毫秒内处理音频的示例
-
借鉴过去的经验 | 拿出处理程序,提出问题。
-
带可执行演示的 wav2midi 音乐旋律提取算法
-
javascript 基础教程 [向过去的教程学习]