今日算法之_24_整数反转
前言
Github:https://github.com/HealerJean
1、整数反转
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
注意:假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
1.1、解题思路
一般情况下 除以10 运算即可,但是基于上面的注意,我们一定要考虑整数溢出
溢出条件有两个
大于整数最大值
MAX_VALUE = 2^31-1 = 2147483647
,小于整数最小值
MIN_VALUE = -2^31 = -2147483648
,
从 rev * 10 + pop > MAX_VALUE
这个溢出条件来看
当出现 `ans > MAX_VALUE / 10 `,则一定溢出
比如:res = 214748365 -> res * 10 = 2147483650 > 2147483641 溢出
当出现 `ans == MAX_VALUE / 10` ,但是有余数 且 pop > 7 时,则一定溢出,7是 2^31-1的个位数
比如 res = 214748364 pop > 7 => 214748364 * 10 + 8 = 2147483648 则肯定溢出
从 rev * 10 + pop < MIN_VALU
E这个溢出条件来看
当出现 ans < MIN_VALUE / 10 ,则一定溢出
当出现 ans == MIN_VALUE / 10 且 pop < -8 时,则一定溢出,8是-2^31的个位数
1.2、算法
1.2.1、算法1
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = 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;
x = x / 10;
}
return rev;
}
1.2.2、算法2:
public int reverse (int x){
int res = 0;
while(x != 0){
int p = x % 10;
int m = res * 10 + p ; // 3
int j = res * 10 / 10 ;
if (j != res){
return 0 ;
}
res = m;
x = x / 10;
}
return res;
}
1.3、测试
@Test
public void test(){
System.out.println("Integer.MIN_VALUE:"+Integer.MIN_VALUE);
System.out.println("Integer.MAX_VALUE:"+Integer.MAX_VALUE);
System.out.println(reverse(521));
}
Integer.MIN_VALUE:-2147483648
Integer.MAX_VALUE:2147483647
125