leetcode 7. 整数反转（Java版）

作者: M_lear | 来源:发表于2019-02-22 17:11 被阅读0次

题目描述（题目难度，简单）

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 $[−2^{31}, 2^{31} − 1]$ 。请根据这个假设，如果反转后整数溢出那么就返回 0。

示例代码

class Solution {
    public int reverse(int x) {
        long y = x;
        long res = 0;
        do{
            res = 10*res + y % 10;
        }while((y /= 10) != 0);
        if(res < Integer.MIN_VALUE || res > Integer.MAX_VALUE){
            return 0;
        }
        return (int)res;
    }
}

思路解析

这个题的题目难度虽然被划为简单，但是这一题提交的正确率却是前 7 题里最低的。

image.png
所以我们不能小看它，这个题我原来在一次机试考试中也遇到过，也顺利的解决了。所以最开始我也看轻了这道题，提交好几次都没通过。问题就出在这个题加了可能溢出这个条件，开始我还想有没有比较巧妙的办法，提前判断反转后会不会溢出，想了几个方法，但提交发现都有漏洞。最后突然想到，这个溢出这么难判断的原因就是使用 int 去存反转后的结果，如果溢出就会把溢出部分的数据位丢掉，导致结果不正确。那我们用一个更长的数据类型（long）去存反转后的结果不就行了，这样肯定不会存在有丢掉数据位的情况。最后直接把反转后的结果与 int 类型的上下限比较即可判断是否溢出。
感觉这是最简洁的办法了，也好记。以后面试遇到就这样回答了(^0^)。
帮大家回忆一下 Java 基本数据类型的长度：

类型	长度（字节）
byte	1
short	2
int	4
long	8
float	4
double	8
char	2

还有一点需要注意的就是，Java 数值类型中没有无符号类型
下面也贴出 leetcode 官方给的题解吧，应该算是标准的正解，但饶了点弯，不如上面的代码简洁好记，给大家对比一下，同时给大家多一个思路。

leetcode 官方题解（内容原样复制）

方法：弹出和推入数字 & 溢出前进行检查

思路
我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。
算法
反转整数的方法可以与反转字符串进行类比。
我们想重复“弹出” $x$ 的最后一位数字，并将它“推入”到 $\text{rev}$ 的后面。最后， $\text{rev}$ 将与 $x$ 相反。
要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

但是，这种方法很危险，因为当 $\text{temp} = \text{rev} \cdot 10 + \text{pop}$ 时会导致溢出。
幸运的是，事先检查这个语句是否会导致溢出很容易。
为了便于解释，我们假设 $\text{rev}$ 是正数。

如果 $temp = \text{rev} \cdot 10 + \text{pop}$ 导致溢出，那么一定有 $\text{rev} \geq \frac{INTMAX}{10}$
如果 $\text{rev} > \frac{INTMAX}{10}$ ，那么 $temp = \text{rev} \cdot 10 + \text{pop}$ 一定会溢出。
如果 $\text{rev} == \frac{INTMAX}{10}$ ，那么只要 $\text{pop} > 7$ ， $temp = \text{rev} \cdot 10 + \text{pop}$ 就会溢出。
当 $\text{rev}$ 为负时可以应用类似的逻辑。

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

怎么样，对比后，是不是发现还是第一种方法更简单更好理解一点呢（嘻嘻）。

补充两点知识点*（也挺重要）

一、取余运算和取模运算的异同

这个题目最开始，我还是分正负数来考虑的，因为我印象里记得 %
对正数和负数的运算好像有区别。最后去查了一下，补充在这里。
C/C++ 和 Java 一样，% 是取余运算；而 Python 的 % 是取模运算。
取余运算和取模运算的区别：
对于整型数 $a，b$ 来说，取余运算或者取模运算的方法都是下面两步：

求整数商： $c = a/b$
计算余数或者模： $r = a - c\cdot b$

而两者的区别就在于第一步不同：取余运算在取 $c$ 的值时，向 $0$ 方向舍入，而取模运算在计算 $c$ 的值时，则是向负无穷方向舍入。
例如计算： $-7\%4$
第一步：求整数商，取余运算算出的整数商为 $c=\lceil\frac{-7}{4}\rceil=-1$ ，而取模运算算出的整数商为 $c=\lfloor\frac{-7}{4}\rfloor=-2$
第二步：计算余数和模的公式相同，但因 $c$ 的值不同，取余的结果为 $-7-(-1\times4)=-3$ ，取模的结果为 $-7-(-2\times4)=1$ 。
归纳：当 $a$ 和 $b$ 符号一致时，取余运算和取模运算的结果一样。
当符号不一致时，结果不一样。取余运算结果的符号和 $a$ 一致，取模运算结果的符号和 $b$ 一致。
验证结果如下：
对于 Java 来说，
代码如下：

public class Test {
    public static void main(String[] argus){
        System.out.println("-7 % 4 = "+(-7%4));
        System.out.println("7 % -4 = "+(7%-4));
    }
}

运行结果如下：

image.png

对于 Python 来说，

image.png

参考链接：
https://baike.baidu.com/item/%E5%8F%96%E6%A8%A1%E8%BF%90%E7%AE%97/10739384?fr=aladdin

二、Java 位运算部分知识点

在解这道题的时候，考虑过使用位运算简化代码。虽然最后没用上，但还是记在这吧，万一以后用的上呢。
一、Java 移位运算
<<为左移运算，>>为右移运算（左边补符号位），>>>为无符号右移运算（左边恒补 0），注意 Java 中没有<<<运算符。
二、Java 取绝对值的位运算实现

int abs(int x){
    return (x+(x = x>>31))^x;//有点过于精炼，哈哈        
}

分解一下代码，实际上是有两步，
第一步，令 y = x >> 31
第二步，返回结果 (x+y) ^ y
代码解释如下：

当 x 为正数时，y = 0，则 (x+0) ^ 0 还是 x。
当 x 为负数时，x 右移 31位，左边补符号位 1 ，最终y = 0xFFFFFFFF，也即 y = -1。所以(x+y) ^ y = (x-1)^0xFFFFFFFF = ~(x-1) = -x，perfect！！！

完结撒花

leetcode 7. 整数反转（Java版）

题目描述（题目难度，简单）

示例代码

思路解析

leetcode 官方题解（内容原样复制）

方法：弹出和推入数字 & 溢出前进行检查

补充两点知识点*（也挺重要）

一、取余运算和取模运算的异同

二、Java 位运算部分知识点

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读