7. 整数反转

发表于 更新于 分类于

1. 简介

链接：https://leetcode-cn.com/problems/reverse-integer/

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 $[−2^{31}, 2^{31} − 1]$ ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

1
2
输入：x = 123
输出：321

示例 2：

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

示例 3：

1
2
输入：x = 120
输出：21

示例 4：

1
2
输入：x = 0
输出：0

提示：

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

2. 题解

2.1. 数学换算

以数字 123 为例，我们反转这个整数得到的是 321，从数学的角度看相当于

从上面的式子可以看出，反转数字其实可以看成反转不同数字的量级。我们看看反转的方式

假设我们开始反转 x 中的最后一个数字

注意题目假设了环境不允许存储 64 位整数（有符号或无符号），我们在将每个反转过程中的加法操作可能会导致溢出1，所以在进行这步操作前要先判断 res*10+pop 是否会导致溢出。

  1. 当 $res×10 + pop$ 溢出时，因为 $2^{31}-1=2147483647$，$-2^{31}=-2147483648$，则有：
    • 如果 $x$ 是正数，溢出时相当于 $res×10+pop ＞ \text{MAX}$ ，即 $res ＞ \frac{\text{MAX}-pop}{10} ≥ \frac{\text{MAX}}{10}$ 时溢出，当 $pop$ 为 0 时可以取到等号。因此，当 $res ＞ \frac{\text{MAX}}{10}$ 时，$res×10+pop$ 会溢出，其中 $\text{MAX}=2147483647$ ；
    • 如果 $x$ 是负数，跟上面一样，但是 $\text{MAX}=2147483648$ 。
  2. 当 $res == \frac{\text{MAX}}{10}$ 时，因为 $2^{31}-1=2147483647$，$-2^{31}=-2147483648$，则有：
    • 如果 $x$ 是正数，当 $pop > 7$ 时，$res×10+pop$ 会溢出；
    • 如果 $x$ 是负数，其绝对值可以取到 $2147483648$，当 $pop > 8$ 时，$res×10+pop$ 会溢出。

上面的除法都是整除，比如 $res == \frac{\text{MAX}}{10}$ 后会取整。

根据上述流程，实现的 python 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def reverse(self, x: int) -> int:
        negative = True if x < 0 else False
        x = -x if negative else x
        MAX = 2**(31) if negative else 2**(31) - 1
        MAX_POP = 8 if negative else 7
        res = 0
        while x != 0:
            pop = x % 10
            if (res > MAX//10) or (res == MAX // 10 and pop > MAX_POP):
                return 0
            res = res * 10 + pop
            x //= 10
        res = -res if negative else res
        return res

2.2. 利用字符串

把输入的 x 变成字符串，然后逆序输出，再变成数值，判断是否超过题目要求的整数范围。如果不考虑溢出问题，则：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def reverse(self, x: int) -> int:
        MIN = -2**(31)
        MAX = 2**(31)-1
        negative = True if x<0 else False
        x = str(-x) if negative else str(x)
        res = "0"
        n = len(x)
        for i in range(n-1, -1, -1):
            res += x[i]
        res = -int(res) if negative else int(res)
        res = res if MIN <= res <= MAX else 0
        return res

但是题目假设了环境不允许存储 64 位整数（有符号或无符号），上面的方法先将 x 全部逆序后再转换成数值，可能逆序输出 x 这个操作还没完成时，中间结果已经溢出了，这样其实是不符合题目要求的，可以参考第一种方法，在求和前判断是否会溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reverse(self, x: int) -> int:
        negative = True if x < 0 else False
        x = str(-x) if negative else str(x)
        res = "0"
        n = len(x)
        for i in range(n-1, -1, -1):
            pop = x[i]
            if check(res, pop, negative):
                res += pop
            else:
                return 0
        res = -int(res) if negative else int(res)
        return res

def check(res, pop, negative):
    # 不溢出返回 True，溢出返回 False
    res, pop = int(res), int(pop)
    MAX = 2**(31) if negative else 2**(31)-1
    MAX_POP = 8 if negative else 7
    if (res > MAX // 10) or ( res == MAX // 10 and pop > MAX_POP):
        return False
    return True

参考资料

1. https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode/ ↩