[LintCode] Divide Two Integers

NervosNetwork 發布于2019-08-14 15:16 / 1616人閱讀

摘要：首先，分析溢出條件，設置符號位，然后取絕對值運算。原理如下，被除數，除數，設等于。如，，，所以商里必定有一個的次方存入，然后。然后被除數減去，繼續。此時，，循環結束。再舉一個例子看得懂的版本綜合一下

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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