力扣-7. 整数反转（Reverse Integer）

最后编辑于2025-05-29

7. 整数反转（Reverse Integer）

Easy

给定一个带符号的 32 位整数 x，将 x 的数字部分反转后返回。如果反转后整数溢出（超出有符号 32 位整数范围 [-2^31, 2^31-1]），则返回 0。

假设运行环境不允许使用 64 位整型（signed 或 unsigned）。

示例 1：

输入： x = 123
输出： 321

示例 2：

输入： x = -123
输出： -321

示例 3：

输入： x = 120
输出： 21

约束：

  • -2^{31} <= x <= 2^{31} - 1

题目要点与溢出处理

反转整数的关键在于逐位取出数字并按位构造反转后的结果，同时要在每一步检测是否会造成溢出。因为题目限定不能使用 64 位整型（在某些 OJ 环境下），所以需要用 int 并在乘 10 或加下一位之前判断是否会越界。

一种常见且优雅的判定方法是：在将 res 乘以 10 之前检查 abs(res) > INT_MAX / 10（若为真则一定会溢出），这样可以在溢出发生前返回 0。该方法无需专门处理正负号，因为 % 操作在 C++ 中对负数依然返回负的余数，/ 对负数也按向零截断，按位操作自然成立。

解法一：不使用 long，逐位检测溢出（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0; // 溢出检测
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};
  • 时间复杂度： O(log|x|)（与位数成比例）
  • 空间复杂度： O(1)

说明： 在每次乘 10 之前判断 abs(res) > INT_MAX/10 即可保证后续不会溢出。

解法二：使用 long 做中间值（思路拓展）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res = 10 * res + x % 10;
            x /= 10;
        }
        return (res > INT_MAX || res < INT_MIN) ? 0 : (int)res;
    }
};
  • 时间复杂度： O(log|x|)
  • 空间复杂度： O(1)

备注： 虽然该方法实现简单，但题目要求假设环境不允许使用 64 位整数，因此此方法仅作为思路补充。

关于是否需要等于 INT_MAX/10 的额外判断

有些讨论会问：是否还需要在 res == INT_MAX/10 时进一步判断下一位（比如 x%10 > 7）来决定是否溢出？对于本题的整数范围和按位处理流程，使用 abs(res) > INT_MAX/10 的判断已足够，因为输入 x 本身也是 int，不可能提供使得 res 在等于 INT_MAX/10 时再进一步产生非法情形的越界下一位（详见常见证明）。若采用不使用 abs 的写法，可额外检查 res == INT_MAX/10 && x%10 > 7 或 res == INT_MIN/10 && x%10 < -8。

作者想说的话：
整数翻转题主要考察对位运算/取余、边界与溢出的敏感性。解题思路是逐位提取数字并在每一步进行溢出检测：推荐在乘以 10 或加下一位之前检查是否会越界（例如 abs(res) > INT_MAX/10），若环境允许也可用 64 位整型作为中间值简化实现。