问题描述
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
1
2
输入: 123
输出: 321
示例 2:
1
2
输入: -123
输出: -321
示例 3:
1
2
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
思路
最初的思路
我最开始想到的是利用栈的的先进后出特性，实现反转。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int reverse(int x) {
Stack<Integer> stack = new Stack<Integer>();
int count = 0; //统计数的位数
int newNum = 0;
while (x != 0)
{
int hex = x%10; //余数
stack.push(hex); //推入栈
count++; //位数加一
x = x/10; //去除最后一位。继续运算
}
if ( stack.peek() == 0)
{
stack.pop(); //弹出首字母空元素
count--; //位数减一
}
int num = 1;
while(count != 0)
{
num *= 10;
}
while(!stack.empty())
{
newNum = num*stack.pop();
num /= 10;
}
return newNum;
}
};
粗看一看就知道不行，循环太多了。提交测试，果然超时
正确的思路
要做此题，最基本的就是对 % 和 / 以及数的位关系的理解。
- 以365为例，第一次求余数：
365%10 = 5，那么这个5就应该是反转数的首位。 - 将
365/10 = 36,再次36%10 = 6，这次我们应该 把 5 和 6 组建成 56，也就是5*10 + 6 = 56 - 将
36/10 = 3,再次3%10 = 3，这次我们应该 把 56 和 3 组建成 563，也就是56*10 + 3 = 563
由上述过程我们可以总结归纳出，每次先求出原数的10的余数，然后将原数除以10得到商，结果和余数相乘并加上商，就是我们要的反转数
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int reverse(int x) {
int rev = 0; //反转数
while( x!=0 )
{
int ans = x%10; //余数
x /= 10; //下一位
//溢出问题，最大值/10除不尽，最后会余7
/*
if( rev>Integer.MAX_VALUE/10)
这样判断其实是这道题的最优解：
因为int类型最大数和最小数开头的数字只能是1或2，
所以如果有最后一次循环的话，pop的值一定为1或2，
所以(rev == INT_MAX / 10 && pop > 7)和(rev == INT_MIN / 10 && pop < -8)判断可以省略。
但如果不是int类型就应该加个后面的判断了
*/
if( rev>Integer.MAX_VALUE/10 || rev==Integer.MAX_VALUE/10 && ans > 7)
return 0;
if( rev<Integer.MIN_VALUE/10 || rev==Integer.MIN_VALUE/10 && ans <-8)
return 0;
//更新反转数
rev = rev*10 + ans;
}
return rev;
}
}
注意事项
此处我们要注意溢出的问题
当 temp=rev⋅10+pop 时会导致溢出。
幸运的是，事先检查这个语句是否会导致溢出很容易。
为了便于解释，我们假设 rev 是正数。
- 如果
temp=rev⋅10+pop使得溢出，那么一定会有rev > INTMAX/10;
至于 7 和 -8 是怎么产生的？
以 7 为例：题中要求的最大值是 2^31 − 1,这是int类型的最大值，为 2147483648,当 rev = INTMAX/10，此时 rev = 2147483640,在加上8就溢出了，所以进行控制。
评测结果
