題⽬描述

輸⼊數字 n ，按順序打印出從 1 到最⼤的 n 位⼗進制數。⽐如輸⼊ 3 ，則打印出 1 、2 、3⼀直到最⼤的 3 位數 999 。

1. ⽤返回⼀個整數列表來代替打印
2. n 為正整數

示例1
輸⼊：1
返回值：[1,2,3,4,5,6,7,8,9]

思路及解答

直接計算

不太清楚這道題是要考察什麼（苦笑），⼏乎都是⼀個循環能解決的事情，仔細想了⼀下，也並沒有想到其他⽐較令⼈⽿⽬⼀新的做法，⽤Math.pow(10, n) - 1 取出最⼤的邊界條件

public class Solution {

	public int[] printNumbers(int n) {
		double len = Math.pow(10, n) - 1;
		int[] result = new int[(int) len];
		for (int i = 0; i < len; i++) {
			result[i] = i + 1;
		}
		return result;
	}
}

• 時間複雜度：O(10ⁿ)，需要生成10ⁿ-1個數字
• 空間複雜度：O(10ⁿ)，需要存儲所有數字

當n≥10時，10ⁿ-1會超過int範圍，導致溢出

字符串模擬

針對大數問題，使用字符串來模擬數字的生成。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] printNumbers(int n) {
        if (n <= 0) return new int[0];
        
        // 使用List存儲結果，再轉為數組
        List<Integer> list = new ArrayList<>();
        char[] number = new char[n];  // 存儲當前數字的字符表示
        
        // 遞歸生成所有n位數
        generateNumbers(number, 0, list);
        
        // 轉換為數組（去掉前導0）
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        
        return result;
    }
    
    private void generateNumbers(char[] number, int index, List<Integer> list) {
        if (index == number.length) {
            // 將字符數組轉換為整數
            int num = convertToInt(number);
            if (num != 0) {  // 跳過0
                list.add(num);
            }
            return;
        }
        
        // 當前位置可以填0-9
        for (char c = '0'; c <= '9'; c++) {
            number[index] = c;
            generateNumbers(number, index + 1, list);
        }
    }
    
    private int convertToInt(char[] number) {
        int result = 0;
        boolean leadingZero = true;
        
        for (char c : number) {
            if (c != '0' || !leadingZero) {
                if (leadingZero) leadingZero = false;
                result = result * 10 + (c - '0');
            }
        }
        
        return result;
    }
}

• 時間複雜度：O(n×10ⁿ)
• 空間複雜度：O(n×10ⁿ)

優化版本：

public class Solution {
    public int[] printNumbers(int n) {
        if (n <= 0) return new int[0];
        
        int max = (int) Math.pow(10, n) - 1;
        int[] result = new int[max];
        
        // 直接計算並填充，避免字符串轉換開銷
        for (int i = 0; i < max; i++) {
            result[i] = i + 1;
        }
        
        return result;
    }
    
    // 處理大數的版本（返回字符串列表）
    public String[] printNumbersBig(int n) {
        if (n <= 0) return new String[0];
        
        int max = (int) Math.pow(10, n) - 1;
        String[] result = new String[max];
        
        for (int i = 0; i < max; i++) {
            result[i] = String.valueOf(i + 1);
        }
        
        return result;
    }
}

遞歸回溯

利用遞歸生成所有可能的數字組合。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private List<Integer> result;
    private char[] number;
    
    public int[] printNumbers(int n) {
        if (n <= 0) return new int[0];
        
        result = new ArrayList<>();
        number = new char[n];
        
        // 從第0位開始遞歸生成
        dfs(0);
        
        // 轉換為數組
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }
    
    private void dfs(int index) {
        if (index == number.length) {
            // 將字符數組轉換為整數
            int num = 0;
            boolean isZero = true;
            
            for (int i = 0; i < number.length; i++) {
                if (number[i] != '0' || !isZero) {
                    if (isZero) isZero = false;
                    num = num * 10 + (number[i] - '0');
                }
            }
            
            // 跳過0
            if (num > 0) {
                result.add(num);
            }
            return;
        }
        
        // 當前位置可以填0-9
        for (char c = '0'; c <= '9'; c++) {
            number[index] = c;
            dfs(index + 1);
        }
    }
}

• 時間複雜度：O(10ⁿ)
• 空間複雜度：O(n) - 遞歸棧深度