题目地址:
整数反转

1.题目描述

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

示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21
注意:

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

2.题解

2.1解题思路

首先整数反转，比如123反转成321，可以从个位数往前推，可以写成这样的格式

321=3*100+2*10+1

现在看一下123取余和取商的过程

//先对123取余
int x=123

//pop=3
int pop=x%10;

//对123取商
//bob=12
int bob =x/10;

//对bob取余
//yy=2
int yy= bob%10;

//对bob取商
//dd=1
int dd =bob/10;

//对dd取余
//a=1
int a=dd%10

//对dd取商
//b=0
int b = dd/10

当最后取商值为0的时候循环就结束了，每一次的余数乘以10的N次方，就可以得到反转后的整数。

2.2第一版代码

官方给了java提交的方法定义

class Solution {
   public int reverse(int x) {
   }
}

规定了方法返回值必须为int

2.2.1 保存每次的余数

先考虑全是正整数的情况，对x取绝对值，即可得到全是正整数的情况

Math.abs(x)

然后使用一个list来保存每次除以10的余数，使用一个for循环来做取余和取商的运算，结果保存在lsit中

List<Integer> list = new ArrayList<>();
//其实根据int的限制，i的最大值不会超过10
for (int i = 0; i < Integer.MAX_VALUE; i++) {
            list.add(x%10);
            x = x / 10;
            //当x==0的时候，表明计算到了x的首位数字，循环结束
            if (x == 0) {
                break;
            }
        }

根据上述的步骤我们现在得到了x每次除以10的余数，然后遍历list，乘以相应的次幂，这样就可以得到反转的结果。

2.2.2 计算反转的数

根据list.size(),可以得到该乘以多少个10,

//result定义成long型，是为了防止整型溢出
//最后可以将long转成int
 long   result = 0;
 for (int i = 0; i < list.size(); i++) {
       result+=list.get(i)*power(10,list.size()-1-i);
 }

下面是求幂次方的方法

public long power(long  base, int expoment) {
        long   result = 1;
        for (int i = 0; i < expoment; i++) {
            result *= base;
        }
        return result;
    }

2.2.3 最终的返回值

为了判断入参x是正数还是负数,引入了一个boolean参数,初始值为false,如果x为负数,就设为true

boolean isNegativeNu = false;

x为负的情况:

if (isNegativeNum) {
    return new Long(((0-result)>-2147483648?(0-result):0)).intValue();
 }

上面的result定义成了long型,所以最后返回的时候需要转化为int，负数通过0-result得到。

x为正的情况

return new Long(result<2147483647?result:0).intValue();

这里考虑整形的范围是[-2147483648,2147483647],即：

[-2^31,2^31-1]

超过整形的范围需要返回0,不然会溢出,得到一些奇怪的结果,所以循环的时候result定义成long，先得出结果，等最终返回的时候在转换成int，这样会简单一点。

2.2.3.完整的代码

package com.fc.algorithm.array;

import java.util.ArrayList;
import java.util.List;


public class ReverseTest {
    public static int reverse(int x) {
        boolean isNegativeNum =false;
        if (x==Integer.MIN_VALUE) {
            return 0;
        }
        if (x<0) {
            isNegativeNum =true;
        }
        x= Math.abs(x);
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            list.add(x%10);
            x = x / 10;
            if (x == 0) {
                break;
            }
        }

        long   result = 0;
        for (int i = 0; i < list.size(); i++) {
            result+=list.get(i)*power(10,list.size()-1-i);
        }
        if (isNegativeNum) {
            return new Long(((0-result)>-2147483648?(0-result):0)).intValue();
        }
        return new Long(result<2147483647?result:0).intValue();
    }

    public static long   power(long  base, int expoment) {
        long   result = 1;
        for (int i = 0; i < expoment; i++) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {

        int  reverse = reverse(-2147483648);
        System.out.println(reverse);
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);

        int abs = Math.abs(-2147483648);
        System.out.println(abs);


    }
}

2.2.4.leetcode运行结果

java代码执行

性能差了一点，引入了list，导致内存占用高了一点，运行时间也有点长,有的答案用C++运行耗时0ms;

2.2.5.需要注意的点

1.int范围

刚开始的时候没考虑到int的范围问题，运行的时候频繁溢出,得到一些奇怪的返回值

2.Integer.MIN_VALUE

Integer.MIN_VALUE取绝对值会比Integer.MAX_VALUE大一，也会导致溢出

2.3.第二版代码

2.3.1.改进方向

现在去掉一些判断，去掉list，看看结果会不会好一点
首先去掉正负数的判断,然后去掉list
然后去掉定义的求幂次方的方法
改完之后代码精简了很多

public int reverse(int x) {
        //-10<x<10直接返回
        if (x/10==0) {
            return x;
        }
        long result = 0;
        for (int i = 0; i < 10; i++) {
            //每循环一次，余数就会乘以10，可以达到上面用list统计需要乘以10的多少次幂的效果
            result=result*10+x%10;
            //超过整型范围直接返回
            if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
                return 0;
            }
            x = x / 10;
            if (x==0) {
                break;
            }
        }
        return new Long(result).intValue();
    }

2.3.2.改完之后的性能

根据leetcode执行结果可以看到，运行时间和内存消耗都有提升，不过提升的不太明显，还附带了一次C++代码的执行效果，C++的代码运行效率和内存消耗确实低了很多。

执行结果.png

3.总结

这是一道数学题，反转需要用到数学知识，从后往前乘以10的N次幂即可。主要是限定在整型范围内，需要考虑越界的问题。