Reverse Integer

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 store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution & Analysis

Integer.MAX_VALUE = 2147483647

Integer.MIN_VALUE = -2147483648

LeetCode - Approach Pop and Push Digits & Check before Overflow

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

简而言之就是pop push每个digit，并且在这么做之前检查是否overflow。

We can build up the reverse integer one digit at a time.

Reversing an integer can be done similarly to reversing a string. We want to repeatedly "pop" the last digit off of x and "push" it to the back of the rev. In the end, rev will be the reverse of the x.

To "pop" and "push" digits without the help of some auxiliary stack/array, we can use math.

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

However, this approach is dangerous, because the statement temp = rev⋅10 + pop can cause overflow.

Luckily, it is easy to check beforehand whether or this statement would cause an overflow.

• If temp = rev⋅10 + pop causes overflow, then it must be that rev >= Integer.MAX_VALUE / 10;

• If rev > Integer.MAX_VALUE / 10, then temp = rev * 10 + pop is guaranteed to overflow

• If rev == Integer.MAX_VALUE / 10, then temp = rev * 10 + pop will overflow if and only if pop > 7

Similar logic can be applied when rev is negative.

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

Complexity Analysis

• Time Complexity: O(log(x)). There are roughly log 10 ​ (x) digits in x.

• Space Complexity: O(1)

最简短的方法 - 用Long类型

https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java/165595

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

        return (int) res == res ? (int) res : 0;
    }
}

不使用Long类型

https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java

public int reverse(int x)
{
    int result = 0;

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

    return result;
}