您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

LeetCode 7. 整數反轉：數學解法、溢出處理與位運算優化完整攻略

編輯：Java 綜合教學

LeetCode 7. 整數反轉：數學解法、溢出處理與位運算優化完整攻略

將 32 位有符號整數數字反轉，溢出返回 0。看似簡單，實則包含邊界處理、數學技巧、性能優化多個考點。本文提供數學迭代、字符串轉換、位運算三種解法並深度對比。

題目要求

輸入：32 位有符號整數 x (-2^31 ~ 2^31-1)
輸出：數字反轉後的整數
溢出：超出 [-2^31, 2^31-1] 返回 0
示例：123 → 321, -123 → -321, 120 → 21, 1534236469 → 0 (溢出)

解法一：數學迭代 (標準解，O(log n) 時間，O(1) 空間)

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)
        // 負向溢出：rev < INT_MIN/10 或 (rev == INT_MIN/10 且 pop < -8)
        if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
        if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
        
        rev = rev * 10 + pop;  // 組裝反轉數
    }
    return rev;
}

溢出檢查數學推導

Integer.MAX_VALUE = 2147483647，Integer.MIN_VALUE = -2147483648

下一步 rev * 10 + pop > MAX
等價於 rev > (MAX - pop) / 10
因 pop ∈ [-9, 9]，最嚴格情況 pop = 7 (MAX 尾數 7)
簡化為 rev > MAX/10 || (rev == MAX/10 && pop > 7)
同理負數：pop < -8 (MIN 尾數 -8)

解法二：字符串轉換 (簡潔但較慢，面試可作備選)

public int reverse(String x) {
    StringBuilder sb = new StringBuilder(String.valueOf(Math.abs((long)x)));
    sb.reverse();
    try {
        long val = Long.parseLong(sb.toString());
        if (val > Integer.MAX_VALUE) return 0;
        return x < 0 ? (int)-val : (int)val;
    } catch (NumberFormatException e) {
        return 0;
    }
}

優點：代碼極簡，自動處理前導零
缺點：對象創建多、Long.parseLong 開銷大、面試官通常要求數學解

解法三：位運算優化 (理解整數表示本質)

利用 Integer.MAX_VALUE = 0x7FFFFFFF，Integer.MIN_VALUE = 0x80000000

public int reverseBitwise(int x) {
    int rev = 0;
    while (x != 0) {
        int pop = x & 0xF; // 取低 4 位？不，十進制位運算無直接對應
        // 實際十進制反轉無簡單位運算等價
        // 此處僅展示溢出檢查的位運算寫法
        if ((rev & 0x80000000) != 0) return 0; // 符號位變化檢測 (不完全正確)
        rev = rev * 10 + (x % 10);
        x /= 10;
    }
    return rev;
}

結論：十進制反轉本質是數學運算，位運算無優勢，反而易出錯。標準數學迭代最優。

關鍵測試用例覆蓋

輸入	輸出	說明
123	321	正常正數
-123	-321	負數處理
120	21	尾部零自動去除
0	0	邊界
1534236469	0	反轉 9646324351 > MAX → 溢出
-2147483648	0	MIN_VALUE 絕對值溢出 (無法表示 +2147483648)
2147483647	0	MAX_VALUE 反轉溢出
2147483641	1463847412	反轉不溢出的最大值
-2147483641	-1463847412	反轉不溢出的最小值

性能對比 (JMH, 1000萬次調用)

進階：長整數反轉 (LeetCode 面試延伸題)

public long reverseLong(long x) {
    long rev = 0;
    while (x != 0) {
        int pop = (int)(x % 10);
        x /= 10;
        if (rev > Long.MAX_VALUE / 10 || (rev == Long.MAX_VALUE / 10 && pop > 7)) return 0;
        if (rev < Long.MIN_VALUE / 10 || (rev == Long.MIN_VALUE / 10 && pop < -8)) return 0;
        rev = rev * 10 + pop;
    }
    return rev;
}