LeetCode 回文數字：不使用額外空間判斷整數是否為回文

問題描述

給定一個整數，判斷它是否為回文數。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。例如，121 是回文，而 123 不是。負數不是回文（如 -1）。

限制條件：不能使用額外空間（即不能將整數轉換為字符串或數組）。

核心思路

既然不能用字符串，我們可以通過數學運算反轉整數的一半或全部數字來比較。但需注意反轉後可能溢出（參考 "Reverse Integer" 題）。更通用的方法是：

• 負數直接返回 false。
• 反轉整數的後半部分，與前半部分比較。若長度為奇數，去掉中間位再比較。

關鍵步驟

1. 排除負數及個位為 0 的非零數（如 10, 100）。
2. 初始化 reverted = 0。
3. 當 x > reverted 時，將 x 的最後一位疊加到 reverted：
   reverted = reverted * 10 + x % 10; x /= 10;
4. 循環結束時，若 x == reverted（偶數位）或 x == reverted / 10（奇數位），則為回文。

代碼實現 (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;
    }
};

複雜度分析

• 時間複雜度：O(log₁₀ n)，即數字位數。
• 空間複雜度：O(1)，僅使用常數級變量。

常見陷阱

• 負數處理：-121 不是回文。
• 溢出風險：反轉整個數字可能超出 int 範圍，反轉一半避免此問題。
• 結尾為 0 的數：10, 100 等不是回文（反轉後會有前導 0）。

這道題考察對整數操作的熟練度與邊界條件處理，反轉一半數字是標準解法。