LeetCode 7. 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

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

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

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−2^31,  2^31 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

思路一

看完题目,脑子里大概有个思路,去除符号后,把数字转换成字符串然后逆向索引,加上原数字的符号,最后判断一下是否在范围内

class Solution:
    def reverse(self, x):
        if x >= 0:
            new_num = str(x)[::-1]
            # 转换为整数,且若开头有0自动去掉
            new_num = int(new_num)
        else:
            new_num = str(x)[:0:-1]
            new_num = - int(new_num)
        return new_num if  -2147483648 <= new_num <= 2147483647 else 0

最后判断是否溢出,原本使用的 2^31 这种形式, 发现时间效率太低,运行时间慢了28ms,也给自己提了个醒,用到的常量还是静态表示效率高,扔一个表达式确实简单,但是偷的懒代码都能找出来。

思路二

可能是自己太菜,总觉得自己第一时间想出来的肯定不是最优解,于是就借鉴了其他同学的答案,思路确实地道!!

什么结构能把数据反转? 栈啊?但是实现一个栈由占用内存,不如直接存到结果中,原数字的个位是反转后的最高位,原数字弹出一位,反转数字整体左移一位(乘10),算完后判断一下范围和符号

class Solution:
    def reverse(self, x):
        x_abs = abs(x)
        res = 0
        while x_abs != 0:
            res = res * 10 + x_abs % 10
            x_abs = x_abs // 10

        boundry = (1 << 31) if x < 0 else (1 << 31) -1
        # boundry = 2147483648 if x < 0 else 2147483647
        if res > boundry:
            res = 0
        return res if x >= 0 else -1*res

只是这里发现,使用移位比常量效率更高,还不确定原因在哪,欢迎大家一起交流。

评论

暂无评论