[LeetCode] 29. Divide Two Integers 兩數(shù)相除

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 division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

這道題讓我們求兩數(shù)相除，而且規(guī)定不能用乘法，除法和取余操作，那么這里可以用另一神器位操作 Bit Manipulation，思路是，如果被除數(shù)大于或等于除數(shù)，則進行如下循環(huán)，定義變量t等于除數(shù)，定義計數(shù)p，當(dāng)t的兩倍小于等于被除數(shù)時，進行如下循環(huán)，t擴大一倍，p擴大一倍，然后更新 res 和m。這道題的 OJ 給的一些 test case 非常的討厭，因為輸入的都是 int 型，比如被除數(shù)是 -2147483648，在 int 范圍內(nèi)，當(dāng)除數(shù)是  -1 時，結(jié)果就超出了 int 范圍，需要返回 INT_MAX，所以對于這種情況就在開始用 if 判定，將其和除數(shù)為0的情況放一起判定，返回 INT_MAX。然后還要根據(jù)被除數(shù)和除數(shù)的正負來確定返回值的正負，這里采用長整型 long 來完成所有的計算，最后返回值乘以符號即可，代碼如下：

解法一：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        long m = labs(dividend), n = labs(divisor), res = 0;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        if (n == 1) return sign == 1 ? m : -m;
        while (m >= n) {
            long t = n, p = 1;
            while (m >= (t << 1)) {
                t <<= 1;
                p <<= 1;
            }
            res += p;
            m -= t;
        }
        return sign == 1 ? res : -res;
    }
};

我們可以通過遞歸的方法來解使上面的解法變得更加簡潔：

解法二：

class Solution {
public:
    int divide(int dividend, int divisor) {
        long m = labs(dividend), n = labs(divisor), res = 0;
        if (m < n) return 0;
        long t = n, p = 1;
        while (m > (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p + divide(m - t, n);
        if ((dividend < 0) ^ (divisor < 0)) res = -res;
        return res > INT_MAX ? INT_MAX : res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(29.兩數(shù)相除)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)兩數(shù)相除內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論