Leetcode 007:整数反转---Python

一、写在前面

之前写过的Leetcode笔记：点击查看
今天给大家分享的是LeetCode 007:整数反转，为面试而生，期待你的加入。

二、今日题目

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

示例：

输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

三、 分析

这个题目看着不怎么难，因为业务逻辑很简单：把一个整数逆置，题目给了数据范围，给了特殊案例，基本思路如下：拿到输入的数据，判断是否为负数，想办法把数据从个位开始与高位互换位置，判断互换位置后的数据是否溢出。

四、解题

• 方法一：int转变为str，然后遍历字符串（Python里int是不可迭代的，所以得转换一下），将原先的高位变成低位。

# -*- coding: utf-8 -*-
"""
@author = 老表
@date = 2019-08-29
@个人公众号 : 简说Python
"""


class Solution:
    def reverse(self, x: int) -> int:
        y = 0  # 返回结果
        j = 0  # 幂指数(位权重)
        flag = 0  # 正负标志位
        if x < 0:   # 处理负数情况
            flag = 1
            x = x * (-1)
        for i in str(x):  # 转变成字符串进行遍历
            # 进行组装，以前的高位变成低位
            y = y + int(i)*pow(10, j)
            j = j + 1
        if y > pow(2, 31)-1:  # 处理溢出情况
            return 0 
        if flag == 1:  # 处理负数情况
            y = -1 * y
        return y

执行结果：

修改一下对负数和幂指数的处理方法，效果会好一点点，但本质上都是O(n)时间复杂度（n为x的位数）：

# -*- coding: utf-8 -*-
"""
@author = 老表
@date = 2019-08-29
@个人公众号 : 简说Python
"""


class Solution:
    def reverse(self, x: int) -> int:
        y = 0 
        j = 0 
        flag = 0   
        for i in str(x):  
            if i == "-":
                flag = 1
                continue
            y = y + int(i)*10**j
            j = j + 1
        if y > 2147483647: 
            return 0
        if flag == 1: 
            y = -y
        return y

• 方法二：

# -*- coding: utf-8 -*-
"""
@author = 老表
@date = 2019-08-26
@个人公众号 : 简说Python
"""
class Solution:
    def reverse(self, x: int) -> int:
        y = 0  # 返回结果
        flag = 0  # 正负标志位
        if x < 0:  # 如果为负，先化为正数
            x = -x
            flag =1
        while x != 0:  # 循环拆解
            pop = x % 10  # 取出低位
            x = x // 10   # 取出剩余
            y = y * 10 + pop   # 连接重组数据，低位变高位
        if y > 2147483647:    # 判断是否溢出
            return 0
        if flag == 1:   # 处理负数情况
            return -y
        return y

• 提交结果
  
  效果依然不理想，对代码稍加改动：

class Solution:
    def reverse(self, x: int) -> int:
        y = 0  # 结果
        while x != 0:  # 遍历拆分
            pop = x % 10  # 取出低位
            x = x // 10   # 取出剩余数
            if x < 0 and pop != 0:  # 如果为负数另做处理
                pop = pop - 10
                x = x + 1
            y = y * 10 + pop   # 重新组装，低位变成高位
        if y < -2147483648:  # 判断溢出
            return 0
        if y > 2147483647:   # 判断溢出
            return 0
        return y

好一点点？！看不怎么出来，确实，从时间复杂度来说还是差不多的，后面的改动需要注意的是对负数的处理：

# 在Python里负数的除法和正数是相反的，取余数会向10靠近，取商会向-∞靠近
例如：
-12 % 10
结果：8
-123 // 10
结果：-13

然而对于本题来说，
-12➗10取余，我们想得到的是-2，
-123➗10取商，我们想得到的是-12
很简单
pop = pop - 10   # 取余后减10
x = x + 1   # 取商后加1

五、疑惑

我今天发现，在Leetcode 上可以看top级的解题方法了，虽然只有代码，也很有参考学习价值。
方法：

提交自己的答案后，会有一个运行时间分布图，点击上面的黄色柱状条即可查看对应运行时间实现的代码了。

top1的解法：感觉？看起来？确实高级，先转为str，然后用了内置的字符串函数startswith（判断正负），然后用到了切片，嗯～原来这样速度比较快～

top2解法：和top1差不多，不同点在于，转换为字符串后，用内置的字符串处理函数rstrip处理了数据，（删除右边的“-”），然后是正负判断。

top3解法：用到的挺多的，正则，abs（取绝对值函数），join（列表链接成字符串函数），reverse（字符串逆置函数），Python里的三目表达式（a if A else b 其中A是个判断表达式），数据转换（int，str）。

# Python里的三目表达式 
# 很棒的一种判断语句书写方法，让代码看起来比较简洁，给大家举个例子
语言描述： 
形式 ： 变量1 = 结果A if 判断表达式1 else 结果B
如果判断表达式1为True ,则变量1 = 结果A 否则 变量1 = 结果B
a = 1 if 3 > 4 else 0
结果 ： 0

top4解法：Python里的三目表达式（a if A else b 其中A是个判断表达式），列表推导式，遍历循环～

其实看过这些top级解法后，我发现，核心思想和我是一样的，只是在实现某个逻辑功能是方法不同，所以这是我要学习的地方，当然Leetcode上还有很多其他解法，欢迎大家去看看，思考出属于自己的代码。

六、结语

没力气了，健身去了，坚持就完了。