打印从1到最大的n位数

本文转载自微信公众号「神奇的打印的程序员」，作者神奇的位数程序员。转载本文请联系神奇的打印的程序员公众号。

前言

有一个数字n，位数我们需要按照顺序输出从1到最大的打印的n位十进制数，例如：n = 3，位数则输出1、打印的2、位数3...一直到最大的打印的3位数999。

本文将将带着大家一起解决这个问题，位数分析解决思路与实现方法，打印的欢迎各位感兴趣的位数开发者阅读本文。

循环解法

当我们过一眼这个问题后，打印的脑海中想到的位数第一个思路肯定是：

先求出这个最大的n位数用一个循环从1开始逐个打印至最大的n位数

很轻松就能写出如下所示的代码：

export default class PrintMaxNumber {

// 通过遍历获取最大值

public traverseForMax(n: number): void {

let maxNumber = 1;

let i = 0;

while (i++ < n) {

// 每次对结果*10，得出最小的打印的网站模板n+1位的值

maxNumber *= 10;

}

// 输出1到最大值-1位置的值，就是n位数的最大值

for (let i = 1; i < maxNumber; i++) {

console.log(i);

}

}

}

这段代码乍一看没啥问题，当n = 3的时候可以正常输出1～999之间的所有值，但是题目中n并没有规定具体范围，当n很大的时候，超出了js可以表示的最大范围，代码将无法运行。

排列解法

上述思路无法解决大数问题，接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0，就会发现n位所有十进制数其实就是n个从0～9的全排列。也就是说，只要我们把数字的每一位都从0～9排列一遍，就得到了所有的十进制数。

全排列使用递归的方式很容易表达，数字的每一位都只可能是0～9中的源码下载一个数，然后设置下一位。递归结束的条件就是我们已经设置了数字的最后一位。

注意：对递归不了解的开发者，请移步我的另一篇文章：递归的理解与实现[1]

接下来，我们来看下实现思路：

准备一个数组用于描述数字的所有位数从0遍历至9，进入循环填充数字的最高位，即数组的0号元素调用递归函数，填充数组其他位置的元素，即除最大位外的其他位递归函数的实现计算下一位，填充数组下一位的值。继续执行递归函数接受三个参数：数字位数组、数字的总位数、当前位基线条件：当前位是最大位的前一位从0遍历至9，进入循环：

我们举个例子，通过一个图来描述下上述思路的执行过程，服务器托管我们用n来描述所求位数，当n=3时，那么递归树就如下所示：

A控制百位，使用递归从0排列至9B控制十位与个位，使用递归从0排列至9

注意：A中的遍历永远只关注最高位数字的排列赋值，B中的遍历关注其它位数字的排列赋值。当执行栈中的B执行完时，则代表其他位已经排列到了9。此时A中的遍历就会继续执行，修改最高位的值。重复上述流程，直至A中的遍历结束，所有的数字也就排列完成了。

提取正确的数字

当递归的基线条件满足时，我们就需要将当前数字位数组中的值打印出来，我们在存储的时候给每一位数字的后面加多了一个0，我们打印时需要进一步处理，取出有效值即可，实现思路如下：

通过遍历，取出数组中每一项字符串的第0号元素从取出的字符串中，从最高位开始遍历找到第一个非0数，将其存起来最后，输出存储的值即可。

实现代码

思路有了，理论也可行，那么代码就能轻松写出来了，如下所示：

export default class PrintMaxNumber {

public maxNumberToStr(n: number): void {

if (n <= 0) return;

const numberStr: string[] = [];

// 控制数字最高位的排列(0 ~ 9)

for (let i = 0; i < 10; i++) {

numberStr[0] = i + "0";

this.printToMaxRecursively(numberStr, n, 0);

}

}

/

**

* 递归获取最大值

* @param numStr 数字位数组

* @param length 数字位数

* @param index 当前位

* @private

*/

private printToMaxRecursively(

numStr: string[],

length: number,

index: number

): void {

if (index === length - 1) {

// 打印

PrintMaxNumber.printNumber(numStr);

return;

}

// 控制数字其他位的排列（0 ~ 9）

for (let i = 0; i < 10; i++) {

const nextIndex = index + 1;

numStr[nextIndex] = i + "0";

this.printToMaxRecursively(numStr, length, nextIndex);

}

}

/

**

* 输出数字位数组中的有效数字

* @param numStr

* @private

*/

private static printNumber(numStr: string[]): void {

const nLength = numStr.length;

let remove0Val = "";

// 筛选除去多余0后的值

// 假设此时的值是3位数，那么对应的数组就为["00","00","10"], 数组每一项值的第0位才是我们需要的值

for (let i = 0; i < nLength; i++) {

const strVal = numStr[i];

// 取数组每一项的第0位

remove0Val += strVal[0];

}

let finalVal = "";

// 是否从0开始

let isBeginning0 = true;

// 筛选出第一个非0值的字符索引

for (let i = 0; i < remove0Val.length; i++) {

// 从0开始的状态为true且当前字符不为0

if (isBeginning0 && remove0Val[i] !== "0") {

// 表示我们已找到第一个非0数，修改状态

isBeginning0 = false;

}

// 当前位的数非0，将其存起来

if (!isBeginning0) {

finalVal += remove0Val[i];

}

}

if (finalVal !== "") {

console.log(finalVal);

}

}

}

测试用例

接下来，我们来测试下当n = 3时，上述代码能否正常运行。

import PrintMaxNumber from "../PrintMaxNumber.ts";

const printNumber = new PrintMaxNumber();

printNumber.maxNumberToStr(3);

运行结果如下所示，符合预期。

image-20220209011016743

示例代码

本文所列举的完整示例代码请移步：

PrintMaxNumber.ts[2]printMaxNumber-test.ts[3]

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

参考资料

[1]递归的理解与实现: https://juejin.cn/post/6844904197612109838

[2]PrintMaxNumber.ts: https://github.com/likaia/algorithm-practice/blob/3e998c85e40f37101e8d47a5eb5a97eb88e6a21d/src/PrintMaxNumber.ts

[3]printMaxNumber-test.ts: https://github.com/likaia/algorithm-practice/blob/3e998c85e40f37101e8d47a5eb5a97eb88e6a21d/src/test-case/printMaxNumber-test.ts

[4]个人网站: https://www.kaisir.cn/