java算法学习笔记

题目描述：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21

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

解题思路：
题目要求，输入负数，也要输出一个符号相同数字相反的整数，输入一个结尾带0的整数输出却不带0，由此可以想到，我们构建一个整型范围内的数字ans，去存目标的符号相同数字相反的整数。
关键代码如下：
int temp = x % 10;
x /= 10;
ans = ans * 10 + temp;

因为翻转数字有这么一个问题，翻转后的数字容易溢出，所以我们还要对ans进行判断，那么如何去判断呢，有两个办法。
1：在整型变量ans溢出之前判断；
我们知道int 整型范围为(-2,147,483,648，2,147,483,647)，在java中可以用Integer类中MAX_VALUE和MIN_VALUE代替；
因为 ans = ans*10+temp，
如果刚好溢出了，就一定有ans*10+temp>Integer.MAX_VALUE,
两边同时除以10，就剩下ans>Integer.MAX_VALUE/10;
temp/10<1,在整型中变为了0；
如果ans==Integer.MAX_VALUE呢，temp就一定要小于7了，
就相当于2,147,483,640+temp；负数也一样，照理推理就好。

所以判断代码如下：
if (ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE / 10 && temp > 7)) return 0;
if (ans < Integer.MIN_VALUE/10 || (ans == Integer.MIN_VALUE / 10 && temp < -8)) return 0;

2：在溢出后再判断；
这个方法就简单许多了，我们只要将ans定义为long类型再判断是否大于Integer.MAX_VALUE就行，记得最后要强制类型转换，因为题目要求返回一个int类型的。

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