LeetCode Reverse Integer：整數反轉與溢出處理

問題描述

反轉 32 位有符號整數的數字。如 123 → 321，-123 → -321。若反轉後溢出（超出 [-2^31, 2^31-1]），返回 0。末尾 0 應被忽略（如 100 → 1）。

解法一：字符串反轉

轉字符串，處理負號，反轉，轉回長整型檢查溢出，再轉 int。簡單但較慢。

解法二：數學方法（推薦）

循環取末位 pop = x % 10，構建結果 rev = rev * 10 + pop，x /= 10。每步檢查 rev 是否超出 INT_MAX/10 或等於 INT_MAX/10 且 pop > 7（正數），負數類似。溢出即返回 0。

代碼實現 (C++)

class Solution {
public:
    int reverse(int x) {
        const int MAX = 0x7fffffff, MIN = 0x80000000;
        long long rev = 0;
        while (x != 0) {
            int pop = x % 10;
            rev = rev * 10 + pop;
            if (rev > MAX || rev < MIN) return 0;
            x /= 10;
        }
        return (int)rev;
    }
};

複雜度分析

• 時間複雜度：O(log |x|) 位數。
• 空間複雜度：O(1)。

總結

數學方法高效且無額外空間。關鍵是在乘 10 前預判溢出，或用長整型暫存結果最後檢查。注意 C++ 負數取模行為（-123 % 10 = -3），直接構建結果即可正確處理負號。