数据结构算法之leetcode Reverse Integer

将一个int数翻转数字,只翻转数字,符号不做处理。

example:
x = 123, return 321
x = -123, return -321

数据越界则返回0

这个比较简单,就是将int的最高位和最低位依次进行调换,如果int中的每个字符都能拿到其索引值,那么就可以根据索引值进行依次对调。但在求每位上的数字时发现得到个位、十位、百位等上的数字的顺序其实就是在给int进行反转,那我只需要将每次得到的值进行依次记录,然后顺序输出就ok了。

按照这个思路,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int reverse(int x) {
// 其实这个思路还有一种更简单的,直接将int转为string,
// 然后利用string中字符的索引进行交换得到反转字符串,然后再判断是否越界
if (x == 0 || x == Integer.MIN_VALUE){
return 0;
}
StringBuffer stringBuffer = new StringBuffer();
if (x < 0){
stringBuffer.append("-");
x = 0 - x;
}
while (x > 0){
int last = x % 10;
x = x / 10;
stringBuffer.append(last);
}
if (Double.parseDouble(stringBuffer.toString()) > Integer.MAX_VALUE
|| Double.parseDouble(stringBuffer.toString()) < Integer.MIN_VALUE){
return 0;
}
return Integer.parseInt(stringBuffer.toString());
}

代码中将符号位单独拿出来,因为符号位不需要反转。但初版是有bug的,函数传入的参数是int,这虽然能保证原始数据不越界,但不能保证反转之后的数值不越界,所以此处用double类型来接受反转之后的数值,然后进行判断是否越界。

其实判断数值是否越界也不用这么麻烦,因为一个int数值越界之后会返回正常位数以内的数值。那么判断一个int数值操作的结果集是否越界只需判断操作之后的结果值按照逆操作而得到的值与操作之前的值是否一样就可以了。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int reverse(int x)
{
int result = 0;
while (x != 0)
{
int tail = x % 10;
// int操作之后的值如果越界怎么处理,什么原则
int newResult = result * 10 + tail;
if ((newResult - tail) / 10 != result)
{ return 0; }
result = newResult;
x = x / 10;
}
return result;
}

Tips

int最大值为2147483647,用二进制表示为0111 1111 1111 1111 1111 1111 1111 1111,使最大值加1运算,其结果用二进制表示为1000 0000 0000 0000 0000 0000 0000 0000,由于int的最高位是符号位,那么这个结果的最高位是1,编码之后的值为-2147483648

如果不考虑越界2147483647 + 1应该是2147483648,但是越界了,按照编码规则,2147483648被编码为-2147483648,那么将-2147483648逆运算也就是减1得到的结果肯定不是2147483647

您的肯定,是我装逼的最大的动力!