本文涉及：数学原理进行出栈操作、python切片反转字符串、取模运算以及求模的原理
最近跑去刷了一下pat，感觉挺适合作为学校课程的同步练习食用。
不管多忙，leetcode还是不过鸽的！(真香？-？)

题目：整数反转

题干：

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

Example1: 

1
2
输入: -123
输出: -321

Example2: 

1
2
输入: 123
输出: 321

Example3: 

1
2
输入: 120
输出: 21

解题思路

第一种解法

我拿到题目后，第一反应是利用堆栈。利用pop把元素逐个弹出并添加到新的数组中，然后转换类型。
需要注意 的是题目中给定了数值的范围，因此我们需要进行判断。
现在看回来，真是种呆逼的写法啊~ 我就不过多解释了(no eyes to see)，照例还是贴个代码吧： 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def reverse(self, x: int) -> int:
        temp_str  = ""
        if x == 0:
            return 0
        target = 1 if x > 0 else -1
        str_len = len(str(x)) if x > 0 else (len(str(x)) -1)
        x = list(str(x))
        for key in range(str_len): 
            temp_str += x.pop()

        
        return (int(temp_str) * target) if -2**31 <= int(temp_str) <= 2**31 - 1 else 0

每次写都知道自己写的是不够完美的，在写的时候我突然记起python有切片操作，不是比这样子更方便吗！

利用切片的优化解法

python的切片功能能快速的操作字符串，这里的原理和上面的大致相同，不过减少了更多的操作。
大致思路就是把int类型转换成string类型，然后用切片将字符串反转。这里需要注意负数的情况！！！然后把字符串转换回去。
代码：

1
2
3
4
5
6
class Solution:
    def reverse(self, x: int) -> int:
        # 当 x < 0 时，反转字符串并去掉尾巴的负号，并在头部加上
        x = str(x)[::-1] if x >= 0 else "-" + str(x)[::-1][:-1]
        x = int(x) if -2**31 <= int(x) <= 2**31 - 1 else 0
        return x

这是我自己能想到的最优解法了，但结果仍然不太理想。

官方解法

看完官方答案后，我总结了可以优化的点：

  1. 出栈操作可以通过数学知识来简化
  2. 并不需要转换类型
  3. 取值范围的判断

出栈操作思路

算法：
反转整数的方法可以与反转字符串进行类比。
我们想重复“弹出” x 的最后一位数字，并将它“推入”到 res 的后面。最后，res 将与 x 相反。
要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。 

1
2
3
4
5
6
7
//pop operation:
pop = x % 10; # 弹出最后一个数字
x /= 10;

//push operation:
temp = res * 10 + pop;
res = temp;

用图片来理解:

取值范围判断思路

解决了堆栈的操作后，就剩下取值范围要解决了。
我们知道取值范围是：[−2^31, 2^31 − 1]. 也就是说它小于2147483647，大于214748364
假设有1147483649这个数字，它是小于最大的32位整数的，但是将这个数字反转过来后就变成了9463847411，这就比最大的32位整数还要大了，这样的数字是没法存到int里面的，所以肯定要返回0(溢出了)。

上图中，绿色的是最大32位整数
第二排数字中，橘子的是5，它是大于上面同位置的4，这就意味着5后跟任何数字，都会比最大32为整数都大。
所以，我们到【最大数的1/10】时，就要开始判断了
如果某个数字大于 214748364那后面就不用再判断了，肯定溢出了。
如果某个数字等于 214748364呢，这对应到上图中第三、第四、第五排的数字，需要要跟最大数的末尾数字比较，如果这个数字比7还大，说明溢出了。
负数同理

这里需要注意！python是向下取整的，也就是说python的取模运算是不准确的。举个栗子： 

1
2
3
4
>>> print(12 % 10)
2
>>> print(-12 % 10)
8

可以看到，python的模运算中，负数部分与我们预想的是不一致的。
通过了解，取模与取余是不一样的！ 非常amazing啊！ 我也是第一次听到，经过了解取模运算的数学表达是这样的：

1
2
# D = x 对 y 取模
D = x - ( x / y) * y

因此由于python是向下取整，所以我们要进行正负判断！

代码实现：

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

总结

  1. 找到了知识漏洞：python是向下取整的！
  2. 明白了取模的数学原理

参考资料

LeetCode: https://leetcode-cn.com/