题目地址:https://leetcode.com/problems/reverse-integer/description/

题目描述

给定一个 32 位有符号整数,将整数中的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意: 假设我们的环境只能存储 32 位有符号整数,其数值范围是 $[−2^{31}, 2^{31} − 1]$。根据这个假设,如果反转后的整数溢出,则返回 0。

解题思路

刚开始的思路是先把输入数字转换成字符串,用字符串中的[::-1]实现反转。然后把题目中的输入例子分成2种情况:

  • 正整数,判断该正整数反转后的数值范围是否在$[−2^{31}, 2^{31} − 1]$内,如果在,反转后返回;如果不在,返回0。
  • 负数,第一位是-号,从第二位到最后一位进行反转:x[1:][::-1],然后首位加上-号。然后判断反转后的数值范围。

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
x = str(x)
if x[0] == '-':
res = int('-'+x[1:][::-1])
if res < (-2**31) or res > 2**31-1:
return 0
return res
res = int(x[::-1])
if res < (-2**31) or res > 2**31-1:
return 0
return res

在评论区看到了同样采用字符串反转的方法,但是实现的代码比我写的精巧,如下:

1
2
3
4
5
class Solution2(object):
def reverse(self, x):
sign = (x > 0) - (x < 0)
r = int(str(x*sign)[::-1])
return sign*r * (r < 2**31)

如果x是正数,则x>0为True(1),x<0为False(0),标志sign为1;x为负数,则sign为-1。通过sign来控制x和结果值r的正负。
在返回时候判断r的值是否在范围内,如果在,$r < 2^{31}$为True(1),如果不在,$r < 2^{31}$为False(0)。

第二种思路

也可以不用转字符串来实现反转,使用数据结构中的pop和push操作。对x通过取余数和整除操作,重复弹出x的(pop)最后一位数字,并把这个再推入(push)到结果数字res中,实现反转。

pop过程为:

1
2
pop = x % 10
x = x // 10

push过程为:

1
res = res*10 + pop

实现代码

1
2
3
4
5
6
7
class Solution3(object):
def reverse(self, x):
res, remains = 0, abs(x)
while remains:
res, remains = res*10+remains%10, remains//10
if x < 0: res *= -1
return res if abs(res) < 0x7fffffff else 0

0x7fffffff是16进制表示方法,它的10进制值为2147483647,也就是2**31-1。

测试一下:

1
2
3
4
5
6
7
8
0x7fffffff
Out[23]: 2147483647

2**31
Out[24]: 2147483648

2**31-1
Out[25]: 2147483647