劍指 Offer 面試題 12：打印 1 到最大的 n 位數——大數處理與遞歸實現

《劍指 Offer》面試題 12 考察大數問題處理能力：輸入 n，按順序打印從 1 到最大的 n 位十進制數（如 n=3 打印 1~999）。當 n 較大時，結果超出 long 範圍，必須使用字符串或數組模擬大數運算。

一、核心難點分析

1. 大數表示：用 int[] 或 char[] 存儲每一位數字，下標 0 為最高位或最低位
2. 模擬加 1：從最低位向高位傳播進位，處理 9→0 進位邏輯
3. 終止條件：最高位產生進位（即超出 n 位範圍）時停止
4. 輸出格式：跳過前導 0，不打印如 "001" 這樣的格式

二、數組迭代實現（推薦：空間效率高、無棧溢出風險）

public class PrintOneToMaxNthDigits {

    // 數組模擬 +1 操作，返回是否溢出(達到最大n位數)
    public static boolean increment(int[] number) {
        if (number.length == 0) throw new IllegalArgumentException("Invalid length");
        
        boolean isOverflow = false;
        int carry = 0;
        
        for (int i = number.length - 1; i >= 0; i--) {
            int sum = number[i] + carry;
            if (i == number.length - 1) sum++; // 最低位 +1
            
            if (sum >= 10) {
                if (i == 0) {
                    isOverflow = true; // 最高位進位，結束
                } else {
                    carry = 1;
                    number[i] = 0;
                }
            } else {
                number[i] = sum;
                break; // 無進位，提前結束循環
            }
        }
        return isOverflow;
    }

    // 打印數組，跳過前導0
    public static void printNumber(int[] number) {
        boolean isBeginning = true;
        for (int digit : number) {
            if (isBeginning && digit != 0) isBeginning = false;
            if (!isBeginning) System.out.print(digit);
        }
        System.out.println();
    }

    public static void print1ToMaxOfNDigits(int n) {
        if (n <= 0) return;
        int[] number = new int[n];
        while (!increment(number)) {
            printNumber(number);
        }
    }
    
    public static void main(String[] args) {
        print1ToMaxOfNDigits(3); // 打印 1 到 999
    }
}

三、字符串遞歸實現（思路清晰，適合理解全排列本質）

public class PrintOneToMaxNthDigitsRecursive {
    
    public static void print1ToMaxOfNDigits(int n) {
        if (n <= 0) return;
        char[] number = new char[n];
        // 最高位不能為 0，從 1-9 開始遞歸填充後續位
        for (int i = 1; i <= 9; i++) {
            number[0] = (char)('0' + i);
            printRecursively(number, n, 0);
        }
    }
    
    private static void printRecursively(char[] number, int length, int index) {
        if (index == length - 1) {
            printNumber(number);
            return;
        }
        for (int i = 0; i <= 9; i++) {
            number[index + 1] = (char)('0' + i);
            printRecursively(number, length, index + 1);
        }
    }
    
    private static void printNumber(char[] number) {
        // 同數組版邏輯，跳過前導0(實際上最高位已非0)
        StringBuilder sb = new StringBuilder();
        boolean leading = true;
        for (char c : number) {
            if (leading && c == '0') continue;
            leading = false;
            sb.append(c);
        }
        System.out.println(sb.toString());
    }
}

四、兩種方案對比

五、面試延伸考點

• 大數加法：兩個數組從低位向高位逐位相加，處理進位
• 大數乘法：模擬豎式乘法，中間結果數組長度為 m+n
• 打印 1 到最大 n 位數的時間複雜度：O(10^n)，指數級，僅適合 n 較小(如 n≤6)的演示
• 若面試官問 "如何優化打印性能"：批量緩衝輸出、多線程分段打印、或直接生成文件而非控制台輸出