剑指 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 为正整数

题解1：直接输出，不考虑大数

代码：

class Solution { public int[] printNumbers(int n) { int x = 1; for (int i = 1; i <= n; i++) { x = x * 10; } int[] res = new int[x - 1]; for (int i = 0; i < x - 1; i++) { res[i] = i + 1; } return res; } }

复杂度分析：

时间复杂度：O(10^n)空间复杂度：O(1)

题解2：使用字符串模拟进位（考虑大数情况）

主要思路：

定义一个字符串进位函数，调用一次字符串值加 1 ，返回值为 Boolean，用于判断是否越界在进位函数中使用 for 循环来模拟进位在主函数中使用 while 循环来模拟进位并且去除高位的 0 。

主要流程：

代码：

class Solution { public int[] printNumbers(int n) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) {//初始化字符串 sb.append('0'); } List<Integer> res = new ArrayList<>(); while (!increment(sb)) { //去除高位的 0 int index = 0; while (sb.charAt(index) == '0' && index < sb.length()) { index++; } String temp = sb.toString().substring(index);//从 index 处截取字符串 res.add(Integer.parseInt(temp)); } int[] resArray = new int[res.size()]; for (int i = 0; i < res.size(); i++) { resArray[i] = res.get(i); } return resArray; } //使用字符串模拟进位 public boolean increment(StringBuilder sb) { boolean overflow = false; for (int i = sb.length() - 1; i >= 0; i--) { char c = (char) (sb.charAt(i) + 1);//最低位加1 //接下来判断是否越界 if (c > '9') {//有进位 sb.replace(i, i + 1, "0"); //替换索引为 i 处的字符，i+1 为终止位，不包含终止位 if (i == 0) {//若此时 i==0，则为最高位，说明越界，使标志 overflow=true overflow = true; } } else {//没有进位，直接替换跳出循环 sb.replace(i, i + 1, String.valueOf(c)); break; } } return overflow; } }

参考题解： java剑指offer原题解法

题解3：使用dfs递归（全排列问题，推荐）

递归参数：最大索引 n，当前索引 index，当前字符串 sb，结果集 res

代码：

class Solution { public int[] printNumbers(int n) { List<Integer> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); dfs(n, 0, sb, res); int[] resArray = new int[res.size() - 1]; for (int i = 0; i < res.size() - 1; i++) {//需要消去res 中的第一个元素 0 resArray[i] = res.get(i + 1); } return resArray; } public void dfs(int n, int index, StringBuilder sb, List<Integer> res) { //终止条件判断 if (index == n) { res.add(Integer.valueOf(sb.toString())); return; } for (int i = 0; i <= 9; i++) { sb.append(i); dfs(n, index + 1, sb, res); //回溯，删去该元素，消除影响 if (sb.length() != 0) { sb.deleteCharAt(sb.length() - 1); } } } }

参考题解： java剑指offer原题解法（评论中）