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

LeetCode.007.Reverse Integer


题目描述

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.371.Sum of Two Integers

下一篇 LeetCode.283.Move Zeroes

阅读
898
阅读预计4分钟
创建日期 2018-01-28
修改日期 2018-02-07
类别
百度推荐