LeetCode Palindrome Number：不轉字符串判斷回文數

問題描述

判斷一個 32 位有符號整數是否為回文數。負數不是回文；不能使用額外空間（即不能轉字符串）；反轉整數可能溢出需處理。

核心思路：半數反轉

將整數後一半數字反轉，與前一半比較。具體：

1. 特殊情況：x < 0 或 x % 10 == 0 && x != 0 直接返回 false。
2. 循環反轉後半部：
    reverted = 0;
 while (x > reverted) { reverted = reverted * 10 + x % 10; x /= 10; }
3. 判斷：
    偶數位數字：x == reverted
    奇數位數字：x == reverted / 10（中間位不影響）

此法只反轉一半數字，完全避免溢出，空間 O(1)，時間 O(log₁₀n)。

C++ 實現

class Solution {
public:
    bool isPalindrome(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;
    }
};

關鍵點解析

• x % 10 == 0 && x != 0 排除 10, 100 等以 0 結尾的數（反轉會有前導 0）。
• 循環條件 x > reverted 確保只處理一半位數。
• 最終比較兼容奇偶位數長度。

複雜度

• 時間：O(log₁₀n) — 位數循環。
• 空間：O(1) — 僅用幾個整型變量。

總結

Palindrome Number 考察整數操作技巧，「半數反轉」是標準解法，既滿足空間限制又避免溢出。面試中常作為基礎熱身題，掌握邊界條件處理至關重要。