打印從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排列至9
- B控制十位與個位，使用遞歸從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/
