7. 整数反转
题目描述
输入一个 32 位有符号整数 x。把它的各位数字倒过来排列，符号保持不变，返回得到的整数。倒过来后开头的 0 会自然消失。
如果结果落在 [-2^31, 2^31 - 1] 之外，返回 0。
假设运行环境不能存放 64 位整数，无论有无符号。
示例 1
输入：x = 123 输出：321
示例 2
输入：x = -123 输出：-321
解释：符号保留，数字部分 123 反转为 321。
示例 3
输入：x = 120 输出：21
解释：反转得到 021，前导零去掉后是 21。
数据范围
-2^31 <= x <= 2^31 - 1
解题思路
先记下符号，只处理绝对值。每次用 x % 10 取出最低位 digit，再 x //= 10 去掉它，把 digit 接到 rev 的末尾：rev = rev * 10 + digit。关键在于溢出要在乘 10 之前判断：只有 rev <= (2^31 - 1 - digit) // 10 时，rev * 10 + digit 才不会超过上限。
为什么正确
rev 始终是已弹出数字按反序组成的数，并且始终不超过 2^31 - 1。
复杂度分析
时间 O(log|x|)，即数字位数；额外空间 O(1)。
易错点
先算 rev * 10 + digit 再检查溢出，在 C++/Java 中已经溢出了，结果不可信。必须在推入之前用 (INT_MAX - digit) / 10 比较。另外 abs(-2^31) 在 32 位整数中会溢出，要先转成 64 位或分别处理。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverse(self, x: int) -> int:
sign = -1 if x < 0 else 1
x = abs(x)
rev = 0
while x:
digit = x % 10
x //= 10
if rev > (2**31 - 1 - digit) // 10:
return 0
rev = rev * 10 + digit
return sign * revclass Solution {
public int reverse(int x) {
int sign = x < 0 ? -1 : 1;
long v = Math.abs((long) x);
int rev = 0;
while (v != 0) {
int digit = (int) (v % 10);
v /= 10;
if (rev > (Integer.MAX_VALUE - digit) / 10) {
return 0;
}
rev = rev * 10 + digit;
}
return sign * rev;
}
}class Solution {
public:
int reverse(int x) {
int sign = x < 0 ? -1 : 1;
long long v = llabs((long long)x);
int rev = 0;
while (v) {
int digit = v % 10;
v /= 10;
if (rev > (INT_MAX - digit) / 10) {
return 0;
}
rev = rev * 10 + digit;
}
return sign * rev;
}
};func reverse(x int) int {
sign := 1
if x < 0 {
sign = -1
x = -x
}
rev := 0
for x != 0 {
digit := x % 10
x /= 10
if rev > (math.MaxInt32-digit)/10 {
return 0
}
rev = rev*10 + digit
}
return sign * rev
}var reverse = function(x) {
const sign = x < 0 ? -1 : 1;
x = Math.abs(x);
let rev = 0;
while (x) {
const digit = x % 10;
x = Math.floor(x / 10);
if (rev > Math.floor((2 ** 31 - 1 - digit) / 10)) {
return 0;
}
rev = rev * 10 + digit;
}
return sign * rev;
};function reverse(x: number): number {
const sign = x < 0 ? -1 : 1;
x = Math.abs(x);
let rev = 0;
while (x) {
const digit = x % 10;
x = Math.floor(x / 10);
if (rev > Math.floor((2 ** 31 - 1 - digit) / 10)) {
return 0;
}
rev = rev * 10 + digit;
}
return sign * rev;
}