LeetCode-Reverse Integer

https://leetcode.com/problems/reverse-integer/

LeetCode 最简单的题目之一，不过要好好审题。

比如题目要求—— The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows. 我根本没有看见粗体的 renversed，所以一直对输入是不是符合 32 位整数进行判断，结果闹了很久才明白为啥最后几个 case 没法 a。

复习：32 位有符号整数范围 -2^31~2^31-1，剩下使用 Python 应该没有任何问题。

下面的思路是将数字转换成字符串然后反转：

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sign=1
        if x<0:
            sign=-1
            x=-x
        xRev=int(str(x)[::-1])
        if xRev<2**31:
            return sign*xRev
        else:
            return 0

用时 52ms 换种思路，使用最简单的整除和取余：

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sign=1
        if x<0:
            sign=-1
            x=-x
        elif x==0:
            sign=0
        xRev=''
        while(x>0):
            xRev=xRev+str(x%10)
            x=int(x/10)

        if sign==0 or int(xRev)>=2**31:
            return 0
        else:
            return sign*int(xRev)

因为加了循环，所以用时稍长一些，65ms

使用 Java 编写，因为溢出的问题搞了半天，无奈只好声明了一个 long 的值存放结果，中途判断是否大于 int 的最大值，返回时再转换成 int。

class Solution {
    public int reverse(int x) {
        long res=0;
        boolean isNegative=x<0;
        if(isNegative)
            x=-x;
        while(x>0){
            res=res*10+x%10;
            if(res>Integer.MAX_VALUE)
                return 0;
            x/=10;
        }
        if(isNegative)
            res=-res;
        return (int)res;
    }
}

用时 29ms，算是比较长的了，肯定有办法优化。

之后发现正负号判断其实没啥用，取消了正负号的判断，但是发现还得在是否溢出时候判断正负号：

class Solution {
    public int reverse(int x) {
        long res=0;
        while(x!=0){
            res=res*10+x%10;

            if((x>0 && res>Integer.MAX_VALUE) || (x<0 && res<Integer.MIN_VALUE))
                return 0;
            x/=10;
        }
        return (int)res;
    }
}

苦思冥想后，使用提前判断 res*10 以后的值是否超过边界，但运行时间依旧：

class Solution {
    public int reverse(int x) {
        int res=0;

        while(x!=0){
            if((res>0 && res>Integer.MAX_VALUE/10)||(res<0 && res<Integer.MIN_VALUE/10))
                return 0;
            res=res*10+x%10;
            x/=10;

        }
        return res;
    }
}

这种提前判断溢出的手段比较少见，因为 Java 溢出的问题比较奇怪。一般的溢出直接用和是否小于其中一个加数判断即可（当两个加数都大于 0 的情况下）