算法2：整数反转（考虑反转溢出问题）

题目描述

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例1：

输入: 123
输出: 321

示例2：

输入: -123
输出: -321

示例3：

输入: 120
输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2³¹, 2³¹ − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解题思路和代码

如果这个问题不考虑溢出是很好解决的，刚遇到这个问题的时候通常不能马上想出最优解。

菜鸟的第一个思路

这个思路略微繁琐，但是可行：利用栈，将数依次除以10的余数存入栈中，然后再从栈中取出经过计算反转。这个算法所花费的时间较多，一是出栈入栈，二是计算。

class Solution {
   
    public int reverse(int x) {
   
        int temp=x;
        int sum=0;
        int  i=0;
        int p=0;
        int t=1;
        Stack stack=new Stack();
        while(temp>0){
              
            stack.push(temp%10);
            temp=(int)temp/10;
            i++;
        }
        if(i!=0){
   
            sum=(int)stack.peek();
            stack.pop();
        }
         while(i>1){
    
             p=(int)stack.peek(); 
                    
             sum=sum+p*multiply(t);
             stack.pop();
             i--;
             t++;
         }
        return sum;

    }
    public int multiply(int t){
   
        int s=1;
        for(int i=t;t>0;t++){
   
            s=s*10;
        }
        return s;
    }
}

OK，当我运行的时候，提示代码运行时间过长，说明效率极低。马上我们可以思考，能不能用纯数学解决呢？

菜鸟进阶解题思路

如果我们还是不考虑溢出的话，仔细观察反转前后数字的关系，我们可以用纯数学思维解决。如下代码，假设输入x=123
第一次循环结束：n=0+3=3 x=12
第二次循环结束：n=3*10+2=32 x=1
第三次循环结束：n=32*10+1=321 x=0
结束循环，输出n的值

class Solution {
   
    public int reverse(int x) {
   
        long n = 0;
        while(x != 0) {
   
        //关键代码
            n = n*10 + x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }

}

那么这个算法是不是更加容易理解，而且高效呢？
时间复杂度为O(n)

测试的时候不是用123，而是比较大的数字做反转测试，结果如下：

但是这里有个不足之处，就是没有考虑溢出，如果一个32位机输入数字反转之后超过32位，那么该算法就是存在问题的。

菜鸟学习大神算法

为了方便理解，我们举例子：



所以正数pop>7 负数pop<-8则为溢出
代码：

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

时间复杂度为O(log(n))

体会

所以通过这个简单算法题，我明白算法思路很重要，学习算法不应该仅仅知道或者记住最优解，应该从自己最原始思路出发，一步步思考优化。
菜鸟会继续加油的！

作者：guanpengchn
链接：https://leetcode-cn.com/problems/reverse-integer/solution/hua-jie-suan-fa-7-zheng-shu-fan-zhuan-by-guanpengc/
来源：力扣（LeetCode）