leetcode[7]-反转整数

题目

给定一个 32 位有符号整数,将整数中的数字进行反转。假设我们的环境只能存储 32 位有符号整数,其数值范围是 [ − 2^31 , 2^31 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

示例

  • 输入: 123
  • 输出: 321
  • 输入: -123
  • 输出: -321
  • 输入: 120
  • 输出: 21

python代码:

class Solution(object):
    def __init__(self):
        self.min_int = -pow(2,31)
        self.max_int = pow(2,31)-1
        self.maxint_10 = self.max_int//10
        self.maxint__10 = self.max_int%10
    def reverse(self, x):
        import sys
        """
        :type x: int
        :rtype: int
        """
        rSum = 0
        neg_flag=0
        if x==self.min_int:
            return 0
        if x<0:
            x = -x
            neg_flag=1
        while(x!=0):
            a = x%10
            x = x//10
            if (rSum > self.maxint_10) or (rSum == self.maxint_10 and a>self.maxint__10):
                return 0
            else:
                rSum = rSum*10+a
        if neg_flag:
            rSum = -rSum
        return rSum

这道题重点不在算法,解法比较直观,考察了怎么判断变量值是否溢出,下面根据代码来梳理一下思路:

def __init__(self):
    self.min_int = -pow(2,31)
    self.max_int = pow(2,31)-1
    self.maxint_10 = self.max_int//10
    self.maxint__10 = self.max_int%10

这里提前生成好几个频繁使用的大数,应为reverse函数在系统评测时会频繁调用。

rSum = 0
neg_flag=0
if x==self.min_int:
    return 0
if x<0:
    x = -x
    neg_flag=1

这里为什么要进行最小值的判断呢?在下一段在解释,由于本题的极端情况就是溢出,所以在开始并不需要进行额外的判断,在这里我们要说明一点,也是比较坑爹的一点,关于C++和Python的不同:

c++: 
    int a = -123 % 10; // a = -3
    int b = -123 / 10; // b = -12
python:
    a = -123 % 10 # a = 7
    b = -123 / 10 # b = -13

知道以上区别后,我第一反应是赶紧把负数取反,当作正数来处理,但是你的正数的最大值是2^31-1,而最小值是-2^31,如果给你一个最小值,你直接取反,那就会溢出了,所以需要提前判断一下,若等于最小值,则直接判定为溢出。

while(x!=0):
    a = x%10
    x = x//10
    if (rSum > self.maxint_10) or (rSum == self.maxint_10 and a>self.maxint__10):
        return 0
    else:
        rSum = rSum*10+a

while里面的判断是整个解决方法中最精髓的地方,你要判断的数还不是一下就给你了,而是每循环一次增加着,这就会出现一个问题,你每次增加的时候不能判断是否溢出,只有你增加完后才能进行判断,这就需要我们进行超前判断,就是在溢出值之前就进行判断,提前预知是否可能会溢出。结合本题中数值增长的特点,我们取self.max_int//10做为判断点,如果当前值大于这个数,那么你的下一次增长一定溢出,如果等于,则需要再判断一下预增长的量是否大于self.max_int%10这个值,如果大于则还是会溢出,当上面都不满足的时候才进行增加。

if neg_flag:
    rSum = -rSum

最后,我们再将得到的数根据实际情况求相反数,毕竟我们是把所有数都当作正数处理了。

发表评论

电子邮件地址不会被公开。