0007. 整数反转 #
- 标签:数学
- 难度:中等
一、题目说明 #
描述:给你一个32
位的有符号整数x
,返回将x
中的数字部分反转后的结果。
如果反转后整数超过32
位的有符号整数的范围$[−2^{31},2^{31}−1]$,就返回0
。
假设环境不允许存储 64 位整数(有符号或无符号)。
示例
- 示例 1:
输入:x = 123
输出:321
- 示例 2:
输入:x = -123
输出:-321
- 示例3:
输入:x = 120
输出:21
- 示例4:
输入:x = 0
输出:0
提示
- $-2^{31} <= x <= 2^{31} - 1$
二、解题思路 #
1. 商数余数法 #
想要反转一个数字,就是将这个数字的最低位放到最高位,次低位放到次高位……直至最高位放到最低位,那么就要求:
-
由低位到高位,除以10依次拆解每一个数字;
-
由高位到地位,乘以10依次组合每一个数字;
例如:
先拆解一个数字1347:
-
第一步,先用1347除以10,得商134余数7,这样就获取了第一位数字7;
-
第二步,用上一步的商134再除以10,得商13余数4,这样就获取了第二位数字4;
-
第三步,用上一步的商13再除以10,得商1余数3,这样就获取了第三位数字3;
-
第四步,用上一步的商1再除以10,得商0余数1,这样就获取了第四位数字1;
-
最终,得到的数字顺序为7、4、3、1。
然后再组合:
-
第一步,先用0乘以10,再加上第一个数字7,和为7;
-
第二步,再用第一步的和7乘以10,再加上第二个数字4,和为74;
-
第三步,再用第一步的和74乘以10,再加上第三个数字3,和743;
-
第四步,再用第三步的和743乘以10,再加上第四个数字1,和7431;
这样,就完成了一个数字的反转。
但是由上面的题意可以知道,本题要求我们不能使用long
类型的变量来承接反转后的数字,那么就需要考虑int
类型的范围问题。
比如原数字1234567889,反转后就变成了9887654321,远远超出了Integer.MAX_VALUE
(大约21亿多),按题目要求需要返回0,负数同理。
所以需要在组合的过程中,时时刻刻关注此时的结果大小:
-
如果是正数,且此时已经大于214748364,那么后面若还有正数求和,必然溢出;或者此时已经等于214748364,后面的数字大于7,也会溢出;
-
如果是负数,且此时已经小于-214748364,那么后面若还有负数求和,必然溢出;或者此时已经等于-214748364,后面的数字小于-8,也会溢出;
public int reverse(int x) {
int result = 0;
while(0 != x){
int remainder = x % 10;
//正数
if(result>Integer.MAX_VALUE/10 || result==Integer.MAX_VALUE/10 && remainder>Integer.MAX_VALUE%10){
return 0;
}
//负数
if(result<Integer.MIN_VALUE/10 || result==Integer.MIN_VALUE/10 && remainder<-Integer.MIN_VALUE%10){
return 0;
}
x /= 10;
result = result * 10 + remainder;
}
return result;
}