LeetCode 009 回文數 判斷算法與 Java 實現

LeetCode 009 回文數 判斷算法與 Java 實現

一、題目要求

判斷整數是否為回文數，**不使用額外空間**（即不能轉字符串/數組）。負數直接返回 false。

回文數示例：1, 121, 34543, 345543

二、核心思路：數學提取對稱位

1. 確定最高位 maxLevel (如 12321 → 5 位)
2. 雙指針從兩端向中間：low = 第 i 位, high = 第 (maxLevel+1-i) 位
3. 提取指定位數字：(num / 10^(index-1)) % 10
4. 僅需遍歷至 maxLevel/2

三、完整 Java 實現

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false; // 負數非回文

        // 確定最高位
        int maxLevel = 0, tmp = x;
        while (tmp > 0) { tmp /= 10; maxLevel++; }
        // 注意：x=0 時 maxLevel=0，循環不執行，直接返回 true

        for (int i = 1; i <= maxLevel / 2; i++) {
            int low = getDigit(x, i);
            int high = getDigit(x, maxLevel + 1 - i);
            if (low != high) return false;
        }
        return true;
    }

    // 獲取第 index 位 (從個位起算，1-based)
    private int getDigit(int num, int index) {
        return (int) ((num / Math.pow(10, index - 1)) % 10);
    }
}

四、關鍵細節

五、測試用例

121     → true
-121    → false
10      → false
0       → true
12321   → true
123321  → true
2147483647 → false

六、進階優化：反轉後半部分驗證 (O(logN) 時間, O(1) 空間)

public boolean isPalindromeOptimized(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reverted = 0;
    while (x > reverted) {
        reverted = reverted * 10 + x % 10;
        x /= 10;
    }
    return x == reverted || x == reverted / 10; // 奇數位去掉中間位
}

此法僅反轉一半數字，避免溢出，性能更優。

七、相關鏈接

• LeetCode 官方：Palindrome Number
• GitHub 測試代碼：Q009.java