题目地址:
整数反转
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运行结果
性能差了一点，引入了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++的代码运行效率和内存消耗确实低了很多。
3.总结
这是一道数学题，反转需要用到数学知识，从后往前乘以10的N次幂即可。主要是限定在整型范围内，需要考虑越界的问题。
