7. Reverse Integer

Leetcode Math

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output:  321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

分析

我们可以一次构建反转整数的一位数字：每次弹出和推入一个数字。

• 弹出数字： tail = x%10; x = x/10
• 推入数字： newResult = newResult*10 + tail

难点在于如何判断溢出。官方的解答非常繁琐，其实有一种直接的方法：能不能再转换回原数字

if ((newResult - tail) / 10 != result) return 0;

如果newResult溢出，肯定不能再转换回去了。

public int reverse(int x) {
    int result = 0;
    while (x != 0){
        int tail = x % 10;
        int newResult = result * 10 + tail;
        // check overflow
        if ((newResult - tail) / 10 != result) return 0;
        result = newResult;
        x = x / 10;
    }
    return result;
}

但上述方法是一种trick，在其他情况下应用不好。而且要反复做除法，效率也比较低。下面是我想到的比较通用的一种解法，借鉴自Java库Integer.parseInt()中处理溢出的方法(详见本博客LeetCode 8. String to Integer (atoi)):

public int reverse(int x) {
    boolean isPositive = x > 0 ? true : false; // 是否是整数
    int limit = isPositive ? Integer.MIN_VALUE : -Integer.MAX_VALUE; // 数字下限
    x = isPositive ? x : -x; // 转化为正数
    int multmin = limit / 10; // 数字下限：用来判断乘法溢出
    int result = 0; // 数字反转结果
    int i = 0; // index
    while (x != 0) {
        int tail = x % 10;
        // returns 0 when the reversed integer overflows.
        if (result < multmin) return 0;
        result *= 10;

        // returns 0 when the reversed integer overflows.
        if (result < limit + tail) return 0;
        result -= tail;

        x = x / 10;
    }
    return isPositive ? - result : result;
}

Python

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x<0:
            quotient = -x
            flag = -1
        else: 
            quotient = x
            flag = 1
        reverse = []
        scale = 1
        while quotient != 0:
            quotient, mod = divmod(quotient, 10)
            print(quotient, mod)
            reverse.append(mod)
            scale *= 10

        result = 0
        for i in reverse:
            scale /= 10
            result += scale*i

        result = int(result*flag)
        if result < -2147483647-1 or result > 2147483647:
            return 0
        return result

def reverse(self, x):
    """
    :type x: int
    :rtype: int
    """
    sign = lambda x: x and (1, -1)[x < 0]
    r = int(str(sign(x)*x)[::-1])
    return (sign(x)*r, 0)[r > 2**31 - 1]

记住2147483647