[LeetCode解題攻略] 7. Reverse Integer

這篇文章將解析 LeetCode 題目 7. Reverse Integer，這是一道簡單但容易出錯的數字操作題。題目要求將一個整數反轉後返回，並需考慮邊界條件和溢出情況。讓我們逐步解題，並討論不同的解法。

題目概述

給定一個 32 位整數 x，要求返回將 x 中的數字反轉後的結果。如果反轉後的數字超出 32 位整數的範圍 [-2^31, 2^31 - 1]，則返回 0。

示例：

Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21

Input: x = 0
Output: 0

思路分析

反轉整數的核心在於數字位的操作，關鍵點包括：

1. 符號處理：如果是負數，記得保持反轉後的負號。
2. 溢出檢查：反轉的結果需要保持在 32 位整數範圍內，否則返回 0。
3. 去除末尾的零：例如，120 反轉後應為 21。

解法一：數字反轉 - 使用數學操作

通過數學操作進行反轉，我們可以逐位將數字取出並重新組合：

步驟：

1. 記錄數字的正負號，將 x 轉為正數。
2. 使用一個迴圈逐位取出 x 的最右側數字，並將其添加到 rev 的尾部。
3. 每次將新數字添加到 rev 時，檢查是否超過 32 位整數範圍。
4. 如果超過範圍，返回 0；否則，返回 rev 的結果。

實作 (Python)：

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX, INT_MIN = 2**31 - 1, -2**31
        rev = 0
        sign = -1 if x < 0 else 1
        x = abs(x)

        while x != 0:
            pop = x % 10
            x //= 10
            # 檢查是否會溢出
            if rev > (INT_MAX - pop) // 10:
                return 0
            rev = rev * 10 + pop

        return sign * rev

複雜度分析

• 時間複雜度：O(log(x))，因為我們按位操作，x 的位數越多，操作次數越多。
• 空間複雜度：O(1)，只使用了固定的變數。

這種方法效率高且內存使用少，適合大多數情況。

解法二：轉換為字串處理

另一種方法是將整數轉換為字串，利用 Python 的字串反轉功能。這樣可以快速完成反轉，但需要處理符號和末尾零。

步驟：

1. 將 x 轉換為字串，並去除負號。
2. 使用字串切片反轉字串。
3. 如果原數為負數，反轉後加上負號。
4. 檢查結果是否在範圍內，若不在則返回 0。

實作 (Python)：

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX, INT_MIN = 2**31 - 1, -2**31
        sign = -1 if x < 0 else 1
        rev_str = str(abs(x))[::-1]
        rev = int(rev_str) * sign

        if rev < INT_MIN or rev > INT_MAX:
            return 0
        return rev

複雜度分析

• 時間複雜度：O(n)，n 是整數的位數。
• 空間複雜度：O(n)，需要存儲反轉後的字串。

這種方法簡潔，但佔用較多空間，適合處理 Python 的大整數。

總結

此題主要考察數字處理的基本操作與邊界控制，兩種方法各有優缺點：

• 數學操作法：效率較高，不需要額外空間。
• 字串反轉法：簡潔易懂，但空間需求較大。

希望這篇教學能幫助你更好地理解 Reverse Integer 題目的思路與解法！