0007. 整数反转
题目描述
给你一个 32 位的有符号整数 x，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹ − 1]，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
约束：-2³¹ <= x <= 2³¹ - 1
解题思路
第一步：理解问题本质
反转整数的核心操作是逐位提取末尾数字，逐位拼接到结果的末尾。例如：
x = 123
第 1 步：末尾数字 3，结果 res = 3，x 变为 12
第 2 步：末尾数字 2，结果 res = 32，x 变为 1
第 3 步：末尾数字 1，结果 res = 321，x 变为 0，结束
难点在于：在不使用 64 位整数的前提下，如何在拼接之前就判断结果是否溢出。
第二步：暴力解法——转为字符串
直接将整数转为字符串，反转字符串后再转回整数。
def reverse(x: int) -> int:
sign = -1 if x < 0 else 1
x_str = str(abs(x))[::-1]
result = sign * int(x_str)
if result < -2**31 or result > 2**31 - 1:
return 0
return result
- 时间复杂度：O(d)，d 为 x 的位数（最多 10 位）
- 空间复杂度：O(d)
问题：Python 的整数没有位数限制，但题目明确要求"假设不允许存储 64 位整数"，用字符串转换绕过了这个约束，不符合题意。
第三步：优化——逐位提取，每步检查溢出
核心思想：每次将结果 res 乘以 10 再加上当前末尾数字之前，先检查这次操作是否会溢出 32 位范围。
32 位有符号整数的边界：
- 最大值：
2³¹ - 1 = 2147483647（末位为 7） - 最小值：
-2³¹ = -2147483648（末位为 -8）
在将 digit 追加到 res 之前，检验 res * 10 + digit 是否越界：
- 正数方向：若
res > 214748364，或res == 214748364且digit > 7，则溢出 - 负数方向：若
res < -214748364，或res == -214748364且digit < -8，则溢出
负数取余的处理：Python 的 % 运算符结果符号与除数相同，即 -123 % 10 = 7（不是 -3）。为了让负数的末位数字保持负号，需要使用 x % -10 或手动处理。
第四步：最优解法——逐位提取 + 溢出预判
逐步从 x 中取出末位数字，追加到结果 res 的末尾，每次追加前先做溢出检查，若溢出直接返回 0。
digit = x 的最后一位（正数用 x % 10，负数用 x % -10）
x 去掉最后一位：x = int(x / 10)（用 int() 而非 //，保证负数向零截断）
溢出判断：
正方向：res > 214748364 或 (res == 214748364 且 digit > 7)
负方向：res < -214748364 或 (res == -214748364 且 digit < -8)
追加操作：res = res * 10 + digit
完整代码实现
class Solution:
def reverse(self, x: int) -> int:
res = 0
while x != 0:
# 取末位数字：正数用 % 10，负数用 % -10 保证 digit 为负
digit = x % 10 if x > 0 else x % -10
# 在追加之前检查溢出（避免使用 64 位整数）
if res > 214748364 or (res == 214748364 and digit > 7):
return 0
if res < -214748364 or (res == -214748364 and digit < -8):
return 0
res = res * 10 + digit
x = int(x / 10) # 向零截断，保证负数行为正确
return res
示例推演
示例 1：x = 123（正数）
| 轮次 | x | digit (x % 10) | 溢出检查 | res 更新 |
|---|---|---|---|---|
| 1 | 123 | 3 | res=0，无溢出 | res = 0×10+3 = 3 |
| 2 | 12 | 2 | res=3，无溢出 | res = 3×10+2 = 32 |
| 3 | 1 | 1 | res=32，无溢出 | res = 32×10+1 = 321 |
| — | 0 | — | x=0，循环结束 | — |
返回 321 ✓
示例 2：x = -123（负数）
| 轮次 | x | digit (x % -10) | 溢出检查 | res 更新 |
|---|---|---|---|---|
| 1 | -123 | -123 % -10 = -3 | res=0，无溢出 | res = 0×10+(-3) = -3 |
| 2 | -12 | -12 % -10 = -2 | res=-3，无溢出 | res = -3×10+(-2) = -32 |
| 3 | -1 | -1 % -10 = -1 | res=-32，无溢出 | res = -32×10+(-1) = -321 |
| — | 0 | — | x=0，循环结束 | — |
返回 -321 ✓
溢出示例：x = 1534236469
反转后应为 9646324351，超出 2147483647。
| 轮次 | x | digit | res（追加前） | 溢出检查 |
|---|---|---|---|---|
| 1 | 1534236469 | 9 | 0 | 无溢出，res=9 |
| 2 | 153423646 | 6 | 9 | 无溢出，res=96 |
| 3 | 15342364 | 4 | 96 | 无溢出，res=964 |
| 4 | 1534236 | 6 | 964 | 无溢出，res=9646 |
| 5 | 153423 | 3 | 9646 | 无溢出，res=96463 |
| 6 | 15342 | 2 | 96463 | 无溢出，res=964632 |
| 7 | 1534 | 4 | 964632 | 无溢出，res=9646324 |
| 8 | 153 | 3 | 9646324 | 无溢出，res=96463243 |
| 9 | 15 | 5 | 96463243 | 无溢出，res=964632435 |
| 10 | 1 | 1 | 964632435 | res > 214748364，溢出！ 返回 0 |
返回 0 ✓
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 字符串反转 | O(d) | O(d) | d 为位数，不符合"不用 64 位整数"的约束 |
| 逐位提取 + 溢出预判 | O(d) | O(1) | 最优解，满足所有约束 |
其中 d 为 x 的十进制位数，32 位整数最多 10 位，因此时间复杂度实际上是 O(1)（常数上界）。
易错点总结
- 负数取余：Python 中
-123 % 10 = 7（非-3），因此负数必须用x % -10来得到带负号的末位数字，否则结果符号会出错。 - 负数整除方向：Python 中
-123 // 10 = -13（向下取整），而题目要求向零截断（即-123 / 10 = -12）。必须使用int(x / 10)而非x // 10。 - 溢出检查的边界值：
214748364 = 2147483647 // 10，正数末位临界为7，负数末位临界为-8（对应-2147483648的末位）。这两个数值需要记准，不能写成8或-7。 - 溢出检查的时机：必须在
res = res * 10 + digit之前检查，检查的是追加后会不会溢出，因此判断的是当前res是否超过214748364（即追加后res * 10是否超过2147483640）。
扩展思考
1. 为什么不允许使用 64 位整数？
这是题目对算法设计的限制，模拟某些底层环境（如嵌入式系统）只有 32 位寄存器的场景。解题思路要求在运算过程中始终保持在 32 位范围内，靠提前检测溢出来实现这一点。
2. 通用溢出检测模式
在对 32 位整数做 res = res * 10 + digit 之前，判断是否溢出的公式：
正数溢出：res > INT_MAX // 10 或 (res == INT_MAX // 10 且 digit > INT_MAX % 10)
负数溢出：res < INT_MIN // 10 或 (res == INT_MIN // 10 且 digit < INT_MIN % 10)
这一模式同样适用于下一道题（atoi 字符串转整数）。
3. 相关题目
- 8. 字符串转换整数 atoi——同样涉及逐位构建数字和溢出处理
- 9. 回文数——判断整数是否是回文，同样用到逐位提取的技巧