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

題目大意

給定一個 32 位有符號整數，將其數字順序反轉。若反轉後超出 [-2^31, 2^31-1] 範圍，返回 0。範例：123 → 321，-123 → -321，120 → 21。

解題關鍵點

1. 處理尾部 0：自然被除法過程忽略（120 % 10 = 0，商 12，下輪處理 12）。
2. 溢出檢測：使用 long long (或 int64_t) 暫存結果，最後判斷是否超出 INT_MAX / INT_MIN。
3. 負數處理：取絕對值運算，最後依原符號加負號。

參考代碼 (Java)

public class Solution {
    public int reverse(int x) {
        if (x == 0) return 0;
        long res = 0;
        int val = Math.abs(x);
        while (val > 0) {
            res = res * 10 + val % 10;
            val /= 10;
        }
        if (res > Integer.MAX_VALUE) return 0;
        return x > 0 ? (int)res : (int)-res;
    }
}

進階：不使用 long long 的溢出檢測 (C++)

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            // 檢測正向溢出：rev > INT_MAX/10 或 (rev == INT_MAX/10 且 pop > 7)
            if (rev > INT_MAX/10 || (rev == INT_MAX/10 && pop > 7)) return 0;
            // 檢測負向溢出：rev < INT_MIN/10 或 (rev == INT_MIN/10 且 pop < -8)
            if (rev < INT_MIN/10 || (rev == INT_MIN/10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

複雜度分析

• 時間複雜度：O(log₁₀|x|) — 位數決定循環次數。
• 空間複雜度：O(1) — 僅使用常數額外變數。

總結

本題是基礎數字操作與邊界條件處理的經典練習。面試時建議先寫 long long 版本確保邏輯正確，再補充「不使用 64 位整數」的溢出檢測技巧，展示對整數表示範圍的深入理解。