LeetCode 回文數字判斷：三種解法深度解析

問題描述

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

解法一：字符串轉換法

最直觀的方法是將整數轉換為字符串，然後雙指針從首尾向中間比較。雖然實現簡單，但需要額外的 O(n) 空間存儲字符串，不符合「不使用額外空間」的進階要求。

解法二：整數反轉法

將整數完全反轉後與原數比較。需注意反轉過程中可能發生整數溢出（超出 32 位有符號整數範圍），需使用 long 類型或邊界檢查來規避。

解法三：逐位比較法（推薦）

不斷取出整數的最高位和最低位進行比較，相等則移除這兩位繼續比較。此法無需額外空間，也無溢出風險，時間複雜度 O(log n)，空間複雜度 O(1)。

核心代碼實現（C++）

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false; // 負數不可能是回文
        int div = 1;
        while (x / div >= 10) div *= 10; // 找到最高位的權重
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10; // 移除最高位和最低位
            div /= 100;
        }
        return true;
    }
};

關鍵點總結

• 負數直接返回 false
• 利用除數 `div` 定位最高位，避免使用 `pow` 浮點運算
• 每次迴圈移除兩位數字，`div` 相應除以 100
• 處理邊界情況：個位數、以 0 結尾的數字（如 10）

此解法優雅地解決了空間限制和溢出問題，是面試中的標準答案。