整数反转reverse-integer
题目
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
- 示例 1:
输入: 123
输出: 321 - 示例 2:
输入: -123
输出: -321 - 示例 3:
输入: 120
输出: 21 -
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围
为 [−2^31, 2^(31 − 1)]。请根据这个假设，如果反转后整数溢出，那么就返回 0。
package reverse_integer;
class Solution {
public int reverse(int x) {
boolean isNegative = false;
if(x<0) {
x = -x;
isNegative = true;
}
String s = x+"";
StringBuffer sbuff = new StringBuffer();
int len = s.length();
for (int j = len-1; j >=0; j--) {
sbuff.append(s.charAt(j));
}
int b = Integer.parseInt(sbuff.toString());
if(isNegative) {
b = -b;
}
return b;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reverse(-1534236469));
}
}
没想到报错了
Exception in thread "main" java.lang.NumberFormatException: For input string: "9646324351"
at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
at java.lang.Integer.parseInt(Integer.java:583)
at java.lang.Integer.parseInt(Integer.java:615)
at reverse_integer.Solution.reverse(Solution.java:17)
at reverse_integer.Solution.main(Solution.java:28)
正解
很明显，上面写的代码没有考虑到反转后整数溢出的问题，所以直接通过拼接字符串来进行反转是不行的。只能一位位取出来，拼接。
那好，第一个问题来了。怎么取出个位呢，计算机显示没有我们这么聪明，这里用到了一点数学上的技巧。
System.out.println("Integer---213");
System.out.println(213%10);
System.out.println(213/10);
System.out.println("Integer---MAX_VALUE---"+Integer.MAX_VALUE);
System.out.println(Integer.MAX_VALUE%10);
System.out.println(Integer.MAX_VALUE/10);
System.out.println("Integer---MIN_VALUE---"+Integer.MIN_VALUE);
System.out.println(Integer.MIN_VALUE%10);
System.out.println(Integer.MIN_VALUE/10);
运行得
Integer---213
3
21
Integer---MAX_VALUE---2147483647
7
214748364
Integer---MIN_VALUE----2147483648
-8
-214748364
这里已经比较明显的可以看出来了，十进制内,对10取余数都是该数的个位数。被10除得到个位数前面的数。所以，我们有了这个公式
临时变量 = 临时变量X10 + 新的个位
公式有了，但是怎么判断溢出呢？
为了方便讨论，先假设这个输入的数是一个正整数。看一下我们的公式就会发现，有乘也有加，不管是乘法运算还是加法运算，这个数都会变大，所以判断应该是有两个。
第一，在没有乘10进位之前，就比Integer.MAX_VALUE大的话，明显不能通过。所以，我们可以让Integer.MAX_VALUE除以10，降位来进行比较。
第二，在没有乘10进位之前，这个数最大就是,Integer.MAX_VALUE / 10(如果比这个数大，那么，乘10后，一定溢出，这个在第一步已经拦截了),所以有这个数最大只能是临时变量 == Integer.MAX_VALUE / 10,那么，由2147483640+pop<2147483647可知，pop<7但不会溢出，所以pop>7必定溢出。同理，可以讨论负整数的情况。
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;
}
