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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

LEETCODE 29. Divide Two Integers 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 50. Pow(x, n) 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。