LEETCODE 29. Divide Two Integers 解题思路分析

题目大意：

两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2

说明:

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=29

解题思路分析：

本题要考虑除法的本质，比如a/b，代表了a中包含有多少个b，最笨的方法可以使用a不停的减去b，直到a小于b为止，减法操作的次数即是结果。但是这样做效率很低，比如1亿除以1，我们要循环1亿次，显然执行时会超时。接下来我们考虑一种比较高效的方式。

举个例子，比如计算101除以5，也就是101中包含多少个5，首先101大于5，所以101中至少包含1个5，然后，我们可以将5乘以2，再看101是否大于等于10，以此类推：

101, 5 // 101大于等于5，因此101中至少包含1个5，将5乘以2
101, 10 // 101大于等于10，因此101中至少包含1个10，将10乘以2
101, 20 // 101大于等于20，因此101中至少包含1个20，将20乘以2
101, 40 // 101大于等于40，因此101中至少包含1个40，将40乘以2
101, 80 // 101大于等于80，因此101中至少包含1个80，将80乘以2
101, 160 // 101小于160，退出循环

通过以上的推导，我们知道101中包含一个80，从5变到80，我们乘了16次，因此，101中至少包含了16个5。但这时还没有结束，101与80之间还相差了21，因此我们还需要再看21中包含多少个5才行，同理，按照上述的步骤可得出，21中还包含了4个5，因此，总共101中包含有20个5。

此外还需要注意一点，题目要求不能使用乘法，上面的乘2操作我们需要使用位运算<<来代替。

10 * 2 == 10 << 1

最后还要吐槽一下本题的test case，解题时要考虑到Integer.MAX_VALUE与Integer.MIN_VALUE之间转化会出现int越界。比如 MIN_VALUE / -1。

实现代码：

public int divide(int dividend, int divisor) {
    // 最终结果是否为正数
    boolean mark=dividend>0&&divisor>0||dividend<0&&divisor<0;
    // 将除数与被除数转化为long型正数
    long dividendL=Math.abs((long)dividend);
    long divisorL=Math.abs((long)divisor);
    long res=0; // 返回结果
    // 当被除数大于等于除数时
    while(dividendL>=divisorL){
        // 除数
        long d = divisorL;
        // 被除数中包含除数的个数
        // 因为当前被除数大于等于除数，因此至少包含1个
        long count=1;
        // 当被除数大于等于2倍的除数时
        while(dividendL>=(d<<1)){
            // 除数乘以2
            d=(d<<1);
            // 被除数中包含除数的个数乘以2
            count=(count<<1);
        }
        // 将包含个数累加到返回结果
        res+=count;
        // 被除数减去除数
        dividendL-=d;
    }
    // 如果返回结果大于int最大值
    if(res>Integer.MAX_VALUE){
        // 如果结果是正数，返回int最大值，反之返回int最小值
        return mark?Integer.MAX_VALUE:Integer.MIN_VALUE;
    }
    return mark ? (int)res:(int)-res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.

Memory Usage: 39.1 MB, less than 6.06% of Java online submissions for Divide Two Integers.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-29-divide-two-integers-解题思路分析/