当前位置：首页 > news >正文

剑指offer-77、打印从1到最⼤的n位数

news 2026/3/26 17:16:59

题⽬描述

输⼊数字 n ，按顺序打印出从 1 到最⼤的 n 位⼗进制数。⽐如输⼊ 3 ，则打印出 1 、2 、3⼀直到最⼤的 3 位数 999 。

⽤返回⼀个整数列表来代替打印
n 为正整数

示例1
输⼊：1
返回值：[1,2,3,4,5,6,7,8,9]

思路及解答

直接计算

不太清楚这道题是要考察什么（苦笑），⼏乎都是⼀个循环能解决的事情，仔细想了⼀下，也并没有想到其他⽐较令⼈⽿⽬⼀新的做法，⽤Math.pow(10, n) - 1 取出最⼤的边界条件

public class Solution {public int[] printNumbers(int n) {double len = Math.pow(10, n) - 1;int[] result = new int[(int) len];for (int i = 0; i < len; i++) {result[i] = i + 1;}return result;}
}

时间复杂度：O(10ⁿ)，需要生成10ⁿ-1个数字
空间复杂度：O(10ⁿ)，需要存储所有数字

当n≥10时，10ⁿ-1会超过int范围，导致溢出

字符串模拟

针对大数问题，使用字符串来模拟数字的生成。

import java.util.ArrayList;
import java.util.List;public class Solution {public int[] printNumbers(int n) {if (n <= 0) return new int[0];// 使用List存储结果，再转为数组List<Integer> list = new ArrayList<>();char[] number = new char[n];  // 存储当前数字的字符表示// 递归生成所有n位数generateNumbers(number, 0, list);// 转换为数组（去掉前导0）int[] result = new int[list.size()];for (int i = 0; i < list.size(); i++) {result[i] = list.get(i);}return result;}private void generateNumbers(char[] number, int index, List<Integer> list) {if (index == number.length) {// 将字符数组转换为整数int num = convertToInt(number);if (num != 0) {  // 跳过0list.add(num);}return;}// 当前位置可以填0-9for (char c = '0'; c <= '9'; c++) {number[index] = c;generateNumbers(number, index + 1, list);}}private int convertToInt(char[] number) {int result = 0;boolean leadingZero = true;for (char c : number) {if (c != '0' || !leadingZero) {if (leadingZero) leadingZero = false;result = result * 10 + (c - '0');}}return result;}
}

时间复杂度：O(n×10ⁿ)
空间复杂度：O(n×10ⁿ)

优化版本：

public class Solution {public int[] printNumbers(int n) {if (n <= 0) return new int[0];int max = (int) Math.pow(10, n) - 1;int[] result = new int[max];// 直接计算并填充，避免字符串转换开销for (int i = 0; i < max; i++) {result[i] = i + 1;}return result;}// 处理大数的版本（返回字符串列表）public String[] printNumbersBig(int n) {if (n <= 0) return new String[0];int max = (int) Math.pow(10, n) - 1;String[] result = new String[max];for (int i = 0; i < max; i++) {result[i] = String.valueOf(i + 1);}return result;}
}

递归回溯

利用递归生成所有可能的数字组合。

import java.util.ArrayList;
import java.util.List;public class Solution {private List<Integer> result;private char[] number;public int[] printNumbers(int n) {if (n <= 0) return new int[0];result = new ArrayList<>();number = new char[n];// 从第0位开始递归生成dfs(0);// 转换为数组int[] arr = new int[result.size()];for (int i = 0; i < result.size(); i++) {arr[i] = result.get(i);}return arr;}private void dfs(int index) {if (index == number.length) {// 将字符数组转换为整数int num = 0;boolean isZero = true;for (int i = 0; i < number.length; i++) {if (number[i] != '0' || !isZero) {if (isZero) isZero = false;num = num * 10 + (number[i] - '0');}}// 跳过0if (num > 0) {result.add(num);}return;}// 当前位置可以填0-9for (char c = '0'; c <= '9'; c++) {number[index] = c;dfs(index + 1);}}
}