[LintCode] Divide Two Integers

NervosNetwork 发布于2019-08-14 15:16 / 1455人阅读

摘要：首先，分析溢出条件，设置符号位，然后取绝对值运算。原理如下，被除数，除数，设等于。如，，，所以商里必定有一个的次方存入，然后。然后被除数减去，继续。此时，，循环结束。再举一个例子看得懂的版本综合一下

Problem

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return 2147483647.

Example

Given dividend = 100 and divisor = 9, return 11.

Note

首先，分析溢出条件，设置符号位，然后取绝对值运算。
原理如下，被除数a，除数b，设c等于b。
在b<=a时，令除数c每次乘以2，增大到小于等于被除数a的时候，c乘了几次，商里就会有一个2的几次方。如25 / 4，4 * 4 < 25，4 * 8 > 25，所以商里必定有一个4（2的2次方）存入temp，然后res += temp。
然后被除数a减去c，继续check。a = 25 - 4 * 4 = 9，c = 4 * 2 = 8，所以商里必定有一个8 / 4 = 2（2的1次方）存入temp。此时a = 9 - 8 = 1，a < b，循环结束。res = 4 + 2 = 6，为所求。

再举一个例子:

13 / 3, a = 13, b = 3, c = 3:
c = 3, temp = 1; c = 6, temp = 2; c = 12; temp = 4;
c = 3, res = 4, a = 1, a < b, return res = 4.

Solution

public class Solution {
    public int divide(int dividend, int divisor) {
        long res = 0;
        boolean neg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long a = Math.abs((long)dividend);
        long b= Math.abs((long)divisor);
        while (a >= b) {
            long c = b;
            long temp = 0;
            while (c <= a) {
                temp = temp == 0 ? 1 : temp << 1;
                c = c << 1;
            }
            c = c >> 1;
            a -= c;
            res += temp;
        }
        if (res >= Integer.MAX_VALUE) res = neg ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        else if (neg) res = -res;
        return (int)res;
    }
}

看得懂的版本：

public class Solution {
    public int divide(int dividend, int divisor) {
        boolean isNeg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        if (dividend == 0) return 0;
        if (divisor == 0) return dividend > 0 ? Integer.MAX_VALUE: Integer.MIN_VALUE;
        long A = Math.abs((long)dividend); //long inside Math.abs
        long B = Math.abs((long)divisor);
        if (A < B) return 0;
        int res = 0;
        long ans = helper(A, B);
        if (ans >= Integer.MAX_VALUE) res = isNeg ? Integer.MIN_VALUE : Integer.MAX_VALUE; //distinguish corner cases
        else res = isNeg ? -(int)ans : (int)ans;
        return res;
    }
    public long helper(long A, long B) {
        if (A < B) return 0;
        long sum = B;
        long res = 1;
        while (sum+sum <= A) {
            sum += sum;
            res += res;
        }
        return res + helper(A-sum, B);
    }
}

综合一下

public class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) sign = -1;
        long A = Math.abs((long)dividend);
        long B = Math.abs((long)divisor);
        if (A < B) return 0;
        long res = 0;
        while (A >= B) {
            long sum = B;
            long temp = 1;
            while (sum+sum < A) {
                sum += sum;
                temp += temp;
            }
            A -= sum;
            res += temp;
        }
        if (res >= Integer.MAX_VALUE) res = sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        else res = res * sign;
        return (int)res;
    }
}

私有云 GPU服务器 Integers Divide LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65546.html

[LeetCode] 29. Divide Two Integers

Problem Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer divisi...

fai1017 2019-08-16 13:30 评论0 收藏0
leetcode-29. Divide Two Integers

摘要：题目解析用加减法实现除法用减法，每次累加被减部分，累加商，以一个固定的倍数递增坑注意循环的跳出便捷，的情况要注意。应用累加思想，可以用在提速上，效率提高如果，则是负的，则是正的题目解析：用加减法实现除法用减法，每次累加被减部分，累加商，以一个固定的倍数递增坑：注意 while循环的跳出便捷，= 的情况要注意。应用：累加思想，可以用在提速上，效率提高 Given two ...

darkbaby123 2019-07-30 17:19 评论0 收藏0
[Leetcode] Divide Two Integers 整数整除

摘要：位操作法复杂度时间空间思路我们设想，本来应该的得到余，那么如果我们把忽略余数后分解一下，，也就是，也就是把商分解为，所以商的二进制是。我们可以不断的将乘的一次方，二次方，等等，直到找到最大那个次方，在这里是的四次方。 Divide Two Integers Divide two integers without using multiplication, division and m...

张春雷 2019-08-14 12:46 评论0 收藏0
leetcode29 Divide Two Integers

摘要：题目要求在不使用乘法，除法和求余操作的情况下，计算两个整数相除的结果。如果溢出了，则返回最大值。在这里核心思路是使用逆向二分法和递归的思路来进行计算。在这里我们使用取值范围更广的来处理数值溢出的场景。题目要求 Divide two integers without using multiplication, division and mod operator. If it is o...

cnio 2019-08-16 10:32 评论0 收藏0
leetcode 29 Divide Two Integers

摘要：很容易想到，我们每次用被除数减去除数，进行减法的次数就是最终结果。这道题的采取了一种类似二分查找的思想。除了这些，这道题还要注意一些边界情况的判断，例如除数或被除数为，值溢出等。题目详情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...

马龙驹 2019-08-15 14:49 评论0 收藏0