Java 經典算法 40 題完整解析：從兔子問題到分桃邏輯

前言

本文整理 40 道 Java 經典算法題目，涵蓋遞歸、數論、字串處理、排序查找、集合操作、邏輯推理等核心領域。每題包含題目分析、標準解法、進階優化與實務應用場景，適合面試準備、教學參考與程式設計思維訓練。

題目分類總覽

精選核心題目深度解析

第 1 題：兔子繁殖問題 (費波那契數列)

// 遞歸版 (指數複雜度，教學用)
public static long fibRecursive(int n) {
    if (n <= 2) return 1;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// 迭代版 O(n) 時間 O(1) 空間 (生產環境)
public static long fibIterative(int n) {
    if (n <= 2) return 1;
    long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// 矩陣快速冪 O(log n) (超大 n)
public static long fibMatrix(long n) { /* 矩陣乘冪實作 */ }

關鍵：遞歸未備忘錄會重複計算，實務必用迭代或矩陣快速冪。

第 4 題：質因數分解

public static List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1) factors.add(n);
    return factors;
}
// 90 → [2, 3, 3, 5]

優化：只試除到 √n，剩餘 n > 1 即為最後質因數。

第 6 題：最大公約數 / 最小公倍數 (輾轉相除法)

// 遞歸版
public static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版 (避免棧溢位)
public static int gcdIter(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

// 最小公倍數：lcm(a,b) = a / gcd(a,b) * b (避免溢位先除後乘)
public static long lcm(long a, long b) {
    return a / gcdIter((int)a, (int)b) * b;
}

第 13 題：完全平方數條件搜尋

// x + 100 = a², x + 268 = b² → b² - a² = 168 → (b-a)(b+a) = 168
// 枚舉 168 的因子對
public static void findNumber() {
    for (int d1 = 1; d1 * d1 <= 168; d1++) {
        if (168 % d1 == 0) {
            int d2 = 168 / d1; // d1 = b-a, d2 = b+a
            if ((d1 + d2) % 2 == 0) { // b = (d1+d2)/2 整數
                int b = (d1 + d2) / 2;
                int a = (d2 - d1) / 2;
                int x = a * a - 100;
                System.out.println(x); // 21, 261, 1581...
            }
        }
    }
}

數學轉化比暴力枚舉 10 萬效率高萬倍。

第 37 題：約瑟夫環問題

// 模擬法 O(n*m)
public static int josephusSimulate(int n, int k) {
    List<Integer> circle = new ArrayList<>();
    for (int i = 1; i <= n; i++) circle.add(i);
    int idx = 0;
    while (circle.size() > 1) {
        idx = (idx + k - 1) % circle.size();
        circle.remove(idx);
    }
    return circle.get(0);
}

// 數學遞推法 O(n) - 推薦
// f(1) = 0; f(i) = (f(i-1) + k) % i
public static int josephusMath(int n, int k) {
    int result = 0; // 0-based
    for (int i = 2; i <= n; i++) {
        result = (result + k) % i;
    }
    return result + 1; // 轉 1-based
}

第 40 題：五猴分桃 (中國剩餘定理應用)

// 逆向推導：第 5 猴操作後剩 T5，滿足 (T5 * 5/4 + 1) 為整數
// 通用解：x ≡ -4 (mod 5^5) → 最小正整數解 = 5^5 - 4 = 3121
public static int monkeyPeach(int monkeys) {
    // 逆向迭代
    int peaches = 1; // 最後剩 1 個 (或 0)
    for (int i = 0; i < monkeys; i++) {
        peaches = peaches * monkeys / (monkeys - 1) + 1;
        // 需確保每步整除，實際需從 1 遞增嘗試
    }
    return peaches;
}

// 正確暴力搜尋 (輸出 3121)
public static void findMinPeaches() {
    for (int total = 1; ; total++) {
        int current = total;
        boolean valid = true;
        for (int m = 0; m < 5; m++) {
            if ((current - 1) % 5 != 0) { valid = false; break; }
            current = (current - 1) / 5 * 4;
        }
        if (valid) { System.out.println(total); break; }
    }
}

算法題解題通用模板

public class SolutionTemplate {
    // 1. 輸入處理
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 讀取輸入...
        
        // 2. 核心邏輯
        long start = System.nanoTime();
        Object result = solve(input);
        long elapsed = System.nanoTime() - start;
        
        // 3. 輸出結果
        System.out.println(result);
        System.err.println("Time: " + elapsed/1e6 + " ms");
    }
    
    // 4. 核心方法 (可獨立單元測試)
    static Object solve(InputType input) { /* ... */ }
}

常見陷阱與最佳實踐

總結

這 40 題涵蓋了程式設計基礎的核心思維：**遞歸與迭代轉換、數學建模優化暴力枚舉、資料結構選擇決定效能、邊界條件決定正確性**。建議練習順序：先理解數學原理 → 寫出正確暴力解 → 分析複雜度 → 尋找優化路徑 → 實作優化版 → 測試邊界。養成「先思考再編碼」習慣，算法能力自會精進。