LeetCode Palindrome Number 回文數判斷 數學反轉

問題

判斷整數是否為回文數。負數非回文，不使用額外空間（即不轉字符串）。

方法一：逐位比較（無溢出風險）

1. 計算位數 len
2. 對 i=0..len/2-1，比較第 i 位與第 len-1-i 位
3. 取位：(x / 10^i) % 10

方法二：數學反轉半數（推薦）

反轉後半部分驗證：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return x == rev || x == rev / 10; // 奇/偶長度
    }
};

關鍵點

• x % 10 == 0 && x != 0 排除 10, 100 等尾隨 0 的數
• 循環條件 x > rev 保證只反轉一半
• 奇數長度時中間位在 rev/10 中被忽略
• 無長整型溢出風險（反轉部分 ≤ 原數）

複雜度

• 時間 O(log₁₀ n) —— 位數
• 空間 O(1)