7. Reverse Integer整数反转 (Easy)

Given a 32-bit signed integer, reverse digits of an integer.（将一个32位的有符号的整数的进行反转，注意：反转后可能会溢出，如果溢出，则返回0）

Example 1:

Input: 123

Output: 321

class Solution {
    public int reverse(int x) {
         
        
        int result = 0;
        while(x !=0){
            int t =  x%10 ;
            x = x/10;
          
            int otherResult = result*10;
            //if otherResult overflow 
            if( (otherResult/10 -result)  != 0){
                return 0;
            }
            int newResult= result*10 + t;
             //if newResult overflow 
            if( (newResult -otherResult ) == t ){
                result = result*10 + t;
            }else{
                return 0;
            }
        }
         return result ;
    }
}

Solution

Approach 1: Pop and Push Digits & Check before Overflow

Intuition

We can build up the reverse integer one digit at a time. While doing so, we can check beforehand whether or not appending another digit would cause overflow.

Algorithm

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 $\text{rev}$. In the end, $\text{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$\text{rev}\cdot 10+\text{pop}$  can cause overflow.

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

To explain, lets assume that  rev  is positive.

Similar logic can be applied when  rev is negative.

这里的以java来说：

当X>0:

Integer.MAX_VALUE的值为 2147483647。

如果 temp = rev*10+pop 会溢出，则 rev >=( Integer.MAX_VALUE/10) 。因为pop是个位数，肯定是 0<=pop<=9。此时就需要分两种情况：

当 rev ==( Integer.MAX_VALUE/10) , 即rev == 214748364 ，此时如果 pop>7  ，temp=214748364*10+pop  就会溢出。

当 rev > ( Integer.MAX_VALUE/10) ，此时无论pop等于什么，temp都会溢出。

当X< 0:

Integer.MIN_VALUE的值为-2147483648。

如果 temp = rev*10+pop 会溢出，则 rev <=( Integer.MIN_VALUE/10) 。因为pop是个位数，肯定是 -9<=pop<=0。此时就需要分两种情况：

当 rev ==( Integer.MIN_VALUE/10) , 即rev == -214748364 ，此时如果 pop<-8  ，temp=-214748364*10+pop  就会溢出。

当 rev < ( Integer.MIN_VALUE/10) ，此时无论pop等于什么，temp都会溢出。

Java:

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: $)$. There are roughly log₁₀(x) digits in $x$.
• Space Complexity: O(1).