剑指offer - 17 打印从1到最大的n位数

绝地灬酷狼 2023-02-19 15:26 1阅读 0赞

# 题目描述 #

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1  
输出: \[1,2,3,4,5,6,7,8,9\]

说明：

用返回一个整数列表来代替打印  
n 为正整数

# 思路 #

在leetcode上做的话，由于要求返回 int 类型数组，相当于默认所有数字都在 int32 整型取值范围内，因此不考虑大数越界问题。

## 代码 ##

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

# 大数问题 #

（转载）

实际上，在原作中本题的主要考点是 大数越界情况下的打印。需要解决以下三个问题：

1.  表示大数的变量类型：  
    无论是 short / int / long … 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 **String** 类型。
2.  生成数字的字符串集：  
    使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 “9999” 至 “10000” 需要从个位到千位循环判断，进位 4 次。

观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。

1.  **递归生成全排列**：  
    基于分治算法的思想，先固定高位，向低位递归，当最终的个位已被固定时，添加数字的字符串。例如当 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 开始 ；

以上两个问题的解决方法如下：

**1. 删除高位多余的 0** ：  
字符串左边界定义： 声明变量 start规定字符串的左边界，以保证添加的数字字符串 num\[start:\] 中无高位多余的 0 。例如当 n = 2 时， 1 - 9 时 start = 1 （例如"08"，从下标1开始添加，实际为“8”）， 10 - 99时 start = 0 。

左边界 start变化规律： 观察可知，当输出数字的所有位都是 9 时，则下个数字需要向更高位进 1 ，此时左边界 start需要减 1 （即高位多余的 0 减少一个）。例如当 n = 3 （数字范围 1 - 999）时，左边界 start 需要减 1 的情况有： “009” 进位至 “010” ， “099” 进位至 “100” 。设数字各位中 9 的数量为 nine ，所有位都为 9 的判断条件可用以下公式表示：

**n - start == nine**

统计 nine 的方法： nine 是一个全局变量，固定第 x 位时，当 i = 9则执行 nine = nine + 1 ，并在回溯前恢复 nine = nine - 1。

**2. 列表从 11 开始：**  
在以上方法的基础上，添加数字字符串前判断其是否为 “0” ，若为 “0” 则直接跳过。

解决以上两个问题后，完整代码如下，为了**正确表示大数**而返回字符串：

class Solution { 
        StringBuilder res;
        int nine = 0, start, 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];
            start = n - 1;
            dfs(0);
            res.deleteCharAt(res.length() - 1);
            return res.toString();
        }
        void dfs(int x) { 
            if(x == n) { 
                String s = String.valueOf(num).substring(start);
                if(!s.equals("0")) res.append(s + ",");
                if(n - start == nine) start--;
                return;
            }
            for(char i : loop) { 
                if(i == '9') nine++;
                num[x] = i;
                dfs(x + 1);
            }
            nine--;
        }
    }

转载声明——  
作者：jyd  
链接：[本题题解][Link 1]  
来源：力扣（LeetCode）

[Link 1]: 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/