leetcode_整型反转

发表于

题目
Given a 32-bit signed integer, reverse digits of an integer.

Example 1:
Input: 123
Output: 321

Example 2:
Input: -123
Output: -321

Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

这道题相对来说比较简单，主要有两点需要注意

  1. 数字反转
    数字或者字符串的反转通常都可以使用push和pop操作进行，不同的是，对于字符串，在使用push/pop操作时，不可避免的需要使用额外的存储空间，大小等于字符串的大小；而对于数字，则可以使用数学方法进行，比如对于数字X
    pop操作
    pop = x % 10;
    x = x / 10;
    push操作
    ret = ret * 10 + pop;
    这个操作也是很好理解的，就是不停的对10进行模运算，得到的就是最后一位，然后将上次循环得到的结果乘10（相当于十进制中左移一位），在加上本次循环得到的模结果。
  2. 溢出判断
    本题的溢出判断是比较容易忽略或者考虑情况不全的，这里先介绍一种普遍的做法。根据上面的push操作公式，我们知道，每次循环的结果都是ret = ret 10 + pop;
    如果ret=ret    10+pop导致溢出，那么一定有，ret>=INTMAX/10，这是因为程序里整数除法运算只保留整数部分，int32范围[-2147483648 2147483647], INTMAX/10 = 214748364，如果ret=214748364，那么ret10不一定溢出（需要pop>7），如果ret>214748364，那么ret10一定溢出，如果ret<214748364,那么ret*10一定不溢出
    同理，对于复数也是一样，需要注意的是，负数的最小值是-2147483648，个位是8
    额外多说一句，虽然不是重点，关于正负号的处理，因为代码中用负数除整数或取模，结果都是负数，比如-26/10=-2，-26%10=-6；

综合以上要点，代码就很容易写出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int reverse(int x) {
        int ret = 0;
        while(x != 0) {
            int pop = x % 10;
            x = x/10;
            if(ret > Integer.MAX_VALUE/10 || (ret == Integer.MAX_VALUE/10 && pop > 7)) return 0;
            if(ret < Integer.MIN_VALUE/10 || (ret == Integer.MIN_VALUE/10 && pop < -8)) return 0;
            ret = ret * 10 + pop;
        }
        return ret;
    }
}

More
还有人通过别的方式进行溢出判断或者躲开溢出，比如看到有人将ret设置成long型，保证不会溢出，循环完之后通过ret是否大于Integer.MAX判断是否溢出，该方法虽然更简洁且可以通过测试，代码也更简单，但是原理写明了只能存储32位有符号整形，所以这种方法不符合题意。