LeetCode.007.Reverse Integer

题目描述

007 Reverse Integer
https://leetcode.com/problems/reverse-integer/description/

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 hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

解题过程

这道题3年前用C++做过，现在用java再做一遍。
方法很简单，就是需要注意边界条件，为此我提交了3次才AC，第一次没考虑反转后越界的情况，第二次没考虑Math.abs(Integer.MIN_VALUE)还等于Integer.MIN_VALUE。

用long型避免溢出实现int逆置

我的最终代码是用long型实现的：

class Solution {
    public int reverse(int x) {
        //反转后有可能超过Integer.MAX_VALUE，例如1534236469，所以必须用long存放
        long result=0;
        //Math.abs(-2147483648)结果还是-2147483648，所以必须将参数强转为long型再求绝对值，而且用long存放结果
        long abs = Math.abs((long)x);
        while(abs!=0){
            result = result*10 + abs%10;
            abs = abs/10;
        }
        result = x>0 ? result : -result;
        if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE)//反转后越界，设为0
            result = 0;
        return (int)result;
    }

AC后看Discuss，有人说了，最好不要用long型，因为万一题目要求long型反转那怎么办？所以要尽量只用int类型解决。我想着也是，借助更高级的数据结构不算本事。

更新reverse前判断下次循环是否溢出

但不用long型怎么写真不会，就看别人的代码。见得最多的是如下的代码，速度很快而且很简洁，思想就是在可能发生溢出前进行判断：

public int reverse2(int x) {
    int res = 0;
    while(x != 0){
        //Math.abs(res) >= 214748365，无论原值第一位是什么都会越界
        //必须在更新res值之前判断，否则当最终res*10大于Integer.MAX_VALUE时出错
        if(Math.abs(res) > Integer.MAX_VALUE / 10)
            return 0;
        res = res*10 + x % 10;
        x /= 10;
    }
    return res;
}

非常巧妙，在更新res值之前，用Math.abs(res) >= 214748365判断下一步是否会溢出，如果会溢出的话直接返回0结束循环。
下面分析一下：
Integer.MAX_VALUE值是2147483647，除以10是214748364，如果res绝对值大于214748364，即大于等于214748365，那么下一步乘以10肯定大于等于2147483650，肯定越界，没啥问题。
问题是，这个条件是否太宽泛了？是否漏了某些可能越界的值？
为啥这么说呢？因为32位符号整型能表示的最大值是2147483647，这个条件只判断了大于等于2147483650的会越界，那么2147483648,2147483649这两个小于2147483650但是也越界的值怎么办呢？不是被漏掉了吗？
一开始我也这么想，后来又一想，输入值不可能有这两个，因为这两个值的翻转：8463847412，9463847412本身就无法用32位符号整型来表示。

总结一下几点：

1、不用单独考虑负号，负数对10取模还是负数，例如，-2%10 = -2, -12%10 = -2
2、考虑反转后溢出的情况，32位有符号整型的表示范围为-2147483648 ~ 2147483647，所以如果反转后超出此范围，必须置为0
3、Math.abs(Integer.MIN_VALUE)还等于Integer.MIN_VALUE

不过我还是有进步的，看3年前提交到LeetCode的c++代码，还额外考虑输入值末尾有0的情况，太多此一举了；而且根本就没考虑翻转后会溢出的情况，不知道当时怎么AC的，有可能后来测试用例更严格了吧。

GitHub代码

leetcode-java / problems / _007_ReverseInteger /
https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_007_ReverseInteger

当前位置 : 首页 » 文章分类 : 算法 » LeetCode.007.Reverse Integer