7. Reverse Integer

Medium

Description

給定一個 32 位元有號整數 x，回傳將其數字部分反轉後的結果。如果反轉後溢出 32 位元有號整數範圍 [-2^31, 2^31 - 1]，則回傳 0。

Example:

Input: x = -123 Output: -321

Intuition#

核心思路：逐位取出末位數字 (x % 10)，組裝到結果中 (result * 10 + digit)，每步檢查溢位。

數字反轉的基本操作：取餘數得到末位、除以 10 去掉末位
關鍵難點在於溢位檢測：反轉後可能超出 Int 範圍
在乘 10 之前就要檢查是否會溢位，而不是乘完才檢查（那時已經溢出了）

Approaches#

1: 用 Long 檢查溢位#

概念: 用 Long 型別儲存中間結果，反轉完成後檢查是否在 Int 範圍內
時間複雜度: O(log x) - 數字的位數
空間複雜度: O(1)

class Solution {
    fun reverse(x: Int): Int {
        var num = x
        var result = 0L
        while (num != 0) {
            result = result * 10 + num % 10
            num /= 10
        }
        return if (result < Int.MIN_VALUE || result > Int.MAX_VALUE) 0 else result.toInt()
    }
}

⭐2: 純 Int 溢位檢查#

概念: 不用 Long，在每次乘 10 前檢查 result 是否會溢出 Int 範圍
時間複雜度: O(log x) - 數字的位數
空間複雜度: O(1)

class Solution {
    fun reverse(x: Int): Int {
        var num = x
        var result = 0
        while (num != 0) {
            val digit = num % 10
            num /= 10
            if (result > Int.MAX_VALUE / 10 || (result == Int.MAX_VALUE / 10 && digit > 7)) return 0
            if (result < Int.MIN_VALUE / 10 || (result == Int.MIN_VALUE / 10 && digit < -8)) return 0
            result = result * 10 + digit
        }
        return result
    }
}

Int.MAX_VALUE = 2147483647（末位 7）、Int.MIN_VALUE = -2147483648（末位 -8），所以邊界檢查用 7 和 -8。

補充：字串反轉法

將數字轉字串反轉，再轉回數字。雖然直覺但面試中不建議，因為繞開了溢位處理的核心考點。

class Solution {
    fun reverse(x: Int): Int {
        val sign = if (x < 0) -1 else 1
        val reversed = Math.abs(x.toLong()).toString().reversed()
        return try {
            sign * reversed.toInt()
        } catch (e: NumberFormatException) {
            0
        }
    }
}

🔑 Takeaways#

Pattern: 數字逐位處理（取餘、整除）是反轉 / 迴文數等題目的通用手法
關鍵技巧: 溢位檢查必須在運算之前做，比較 result 與 MAX_VALUE/10 的關係是標準模式