本文涉及:数学原理进行出栈操作、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/