Leetcode 0007. Reverse Integer (python)

7. Reverse Integer

题目

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

• -2³¹ <= x <= 2³¹ - 1

题目大意

将一个 32 位有符号整数的数字部分反转。如果反转后的整数溢出 32 位有符号整数范围 [-2147483648, 2147483647]，返回 0。题目假设环境不允许使用 64 位整数。

---

你选用何种方法解题？

本题的核心操作是逐位弹出和推入数字，唯一的难点在于溢出检测。Python 中整数没有固定位宽，因此有两种处理思路：

方法	核心思路	时间复杂度	说明
方法一：数学取模法（推荐）	循环 x % 10 弹出末位，ans * 10 + digit 推入	O(log₁₀ n)	最优解：纯数学操作，无需字符串转换
方法二：字符串反转法	转字符串 → 反转 → 转回整数	O(log₁₀ n)	代码最短，但依赖 Python 大整数特性

方法一是推荐解：虽然 Python 原生支持大整数使得溢出检测不是硬约束，但题目明确要求"不能使用 64 位整数"，方法一在循环中显式做溢出判断，体现了对底层整数表示的理解。方法二代码更短，但实际面试中考查的就是溢出处理——用 Python 的字符串切片绕过这个考点反而会扣分。

---

解题过程

问题分析

• 输入：32 位有符号整数 x，范围 [-2147483648, 2147483647]
• 输出：反转后的整数，溢出则返回 0
• 关键约束：不能使用 64 位整数存储中间结果

核心洞察

反转整数的本质是一个栈操作——用取模 % 从末尾弹出数字，用乘加 ×10 + digit 推入新数：

x = 123:

第一次: digit = 123 % 10 = 3,  x = 123 // 10 = 12,  ans = 0 * 10 + 3 = 3
第二次: digit = 12 % 10 = 2,   x = 12 // 10 = 1,    ans = 3 * 10 + 2 = 32
第三次: digit = 1 % 10 = 1,    x = 1 // 10 = 0,     ans = 32 * 10 + 1 = 321

x 变为 0，结束。ans = 321 ✓

负数同样适用——Python 的 % 和 // 对负数也能正确处理（取 abs(x) 更安全）。

溢出检测——真正的考点

反转过程中，ans * 10 + digit 可能超过 32 位有符号整数范围。由于不能用 64 位整数，必须在乘法之前预判：

INT_MAX = 2147483647
INT_MIN = -2147483648

在 ans * 10 + digit 之前检查：

正数溢出条件: ans > INT_MAX // 10，或者 ans == INT_MAX // 10 且 digit > INT_MAX % 10 (即 > 7)
负数溢出条件: ans < INT_MIN // 10，或者 ans == INT_MIN // 10 且 digit < INT_MIN % 10 (即 < -8)

具体而言：

• INT_MAX // 10 = 214748364，INT_MAX % 10 = 7
• INT_MIN // 10 = -214748364（Python 向负无穷取整，实际 -2147483648 // 10 = -214748365）……这里需要特别注意。

Python 的除法陷阱：Python 的 // 是 floor division（向负无穷取整），而 C/Java 是 truncation toward zero。因此：

• C 中 -2147483648 / 10 = -214748364
• Python 中 -2147483648 // 10 = -214748365

所以在 Python 实现中，最简单且安全的做法是只处理绝对值，最后再加回符号：

INT_MAX = 2**31 - 1  # 2147483647
ans = 0
sign = 1 if x >= 0 else -1
x = abs(x)

while x != 0:
    digit = x % 10
    # 溢出检查（正数情况）
    if ans > INT_MAX // 10 or (ans == INT_MAX // 10 and digit > 7):
        return 0
    ans = ans * 10 + digit
    x //= 10

return sign * ans

手推演示例

以 x = -123 为例：

初始: x = 123 (取绝对值), ans = 0, sign = -1

步骤1: digit = 123 % 10 = 3
       ans = 0: 检查通过 (0 < 214748364)
       ans = 0 * 10 + 3 = 3,  x = 12

步骤2: digit = 12 % 10 = 2
       ans = 3: 检查通过
       ans = 3 * 10 + 2 = 32,  x = 1

步骤3: digit = 1 % 10 = 1
       ans = 32: 检查通过
       ans = 32 * 10 + 1 = 321,  x = 0

循环结束。返回 sign * 321 = -321 ✓

以溢出边界 x = 1463847412 为例（反转后为 2147483641，不溢出）：

逐位反转: 1463847412 → 2147483641

检查最后一步: ans = 214748364, digit = 1
  ans == INT_MAX // 10 (214748364), digit = 1 <= 7 → 通过 ✓

以溢出案例 x = 1463847413 为例（反转后为 3147483641，溢出）：

逐位反转到倒数第二步: ans = 314748364, digit = 1
  ans = 314748364 > INT_MAX // 10 (214748364) → 溢出！返回 0

---

这些方法具体怎么运用？

方法一：数学取模法（推荐）

数据结构：仅需几个整数变量。

核心逻辑：

1. 记录符号，取绝对值（简化溢出判断）
2. 循环：用 % 10 弹出末位数字，用 ans * 10 + digit 推入
3. 溢出检测（在推入前）：若 ans > INT_MAX // 10 或 ans == INT_MAX // 10 and digit > 7，返回 0
4. 返回 sign * ans

为什么用绝对值？ 避免 Python 的 floor division 带来的负数处理差异。-1 % 10 = 9（Python）而非 -1（C），如果不取绝对值，循环逻辑会出错。

边界情况：

场景	输入	行为	结果
正数正常反转	123	逐位弹出推入	321
负数	-123	取绝对值处理，最后加符号	-321
末尾有零	120	反转后 021 → 21	21
溢出	1534236469	最后一步检测到溢出	0
零	0	x=0 跳过循环，ans=0	0
INT_MIN	-2147483648	取绝对值 2147483648 > INT_MAX，但题目保证输入合法	溢出返回 0

方法二：字符串反转法

核心逻辑：

1. 记录符号
2. 取绝对值转字符串 str(abs(x))
3. 反转字符串 [::-1]
4. 转回整数，检查是否溢出 32 位范围

优点：代码极短，Python 一行搞定核心逻辑。
缺点：完全绕过了溢出检测这个核心考点，面试中会被追问"如果不能用大整数怎么办"。

---

复杂度

方法	时间复杂度	空间复杂度	说明
数学取模法	O(log₁₀ n)	O(1)	数字的位数 = ⌊log₁₀|x|⌋ + 1，最多 10 次循环
字符串反转法	O(log₁₀ n)	O(log₁₀ n)	需要存储字符串表示

两种方法的时间复杂度都是 O(log₁₀ n)，即数字的位数。对于 32 位整数，位数不超过 10，因此实际运行中两种方法都可以视为常数时间。

---

总结与最佳选择

最快算法：数学取模法。虽然两种方法对于 32 位整数都是 O(1)（最多 10 次迭代），但数学取模法没有字符串分配和反转的开销，且体现了对整数底层表示的理解。

工程最优选择：取决于场景：

• 算法面试：数学取模法——这是面试官想看到的答案，展示了溢出检测、边界处理、位宽限制的理解。用字符串法会被追问"不用字符串怎么做？"
• Python 实际开发：字符串反转法一行搞定，Python 的整数无上限，溢出在 Python 中不会发生

一句话：面试写数学取模法展示底层功底，实际写 Python 用字符串一行梭哈。

---

Code

方法一：数学取模法（推荐）

class Solution:
    def reverse(self, x: int) -> int:
        """数学取模法：逐位弹出末位数字，推入新数。
        使用绝对值简化处理，每次推入前做溢出检测。
        时间复杂度 O(log₁₀ n)，空间复杂度 O(1)。
        """
        INT_MAX = 2**31 - 1         # 2147483647
        INT_MAX_DIV10 = INT_MAX // 10  # 214748364
        INT_MAX_LAST = INT_MAX % 10    # 7

        sign = 1 if x >= 0 else -1
        x = abs(x)                  # 取绝对值，统一处理正数逻辑
        ans = 0

        while x != 0:
            digit = x % 10          # 弹出末位数字

            # 溢出检测：在 ans * 10 + digit 之前预判
            if ans > INT_MAX_DIV10:
                return 0
            if ans == INT_MAX_DIV10 and digit > INT_MAX_LAST:
                return 0

            ans = ans * 10 + digit  # 推入新数末尾
            x //= 10                # 移除已处理的末位

        return sign * ans

方法二：字符串反转法（Python 特供）

class Solution:
    def reverse(self, x: int) -> int:
        """字符串反转法：利用 Python 的字符串切片反转。
        仅适用于 Python 等支持大整数的语言，绕过溢出检测。
        时间复杂度 O(log₁₀ n)，空间复杂度 O(log₁₀ n)。
        """
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31

        sign = 1 if x >= 0 else -1
        # 取绝对值 → 转字符串 → 反转 → 转回整数 → 恢复符号
        reversed_num = sign * int(str(abs(x))[::-1])

        # Python 中必需的后置溢出检查（实际不会溢出，仅为符合题意）
        if reversed_num > INT_MAX or reversed_num < INT_MIN:
            return 0
        return reversed_num