LeetCode 029 — Divide Two Integers

Divide Two Integers

https://leetcode.com/problems/divide-two-integers/

题目要求不用乘法、除法和取模运算符，实现整型除法运算。

既然不能用乘法和除法运算符，那么基本思路就是用减法来代替。不过如果用每次循环减一次被除数这种方式，是肯定会超时的。所以要想办法加速运算。

Solution

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long quotient  = 0;
        int flag = 1;
        auto dividend1 = (long long)fabs(dividend);
        auto divisor1 = (long long)fabs(divisor);
        if(dividend < 0) {
            flag = -1;
        }
        if(divisor < 0) {
            flag = flag == 1 ? -1 : 1;
        }

        std::vector<std::pair<long long, long long> > vec;
        long long times = 1;
        while (dividend1 >= divisor1) {
            vec.emplace_back(divisor1, times);
            dividend1 -= divisor1;
            quotient += times;
            divisor1 += divisor1;
            times += times;
        }

        for (int i = vec.size() - 1; i >= 0; --i) {
            while(dividend1 >= vec[i].first) {
                quotient += vec[i].second;
                dividend1 -= vec[i].first;
            }
        }

        if(flag == -1) {
            quotient = -quotient;
        }

        if(quotient > INT32_MAX) {
            return  INT32_MAX;
        }
        else if (quotient < INT32_MIN) {
            return  INT32_MIN;
        }
        return quotient;
    }
};

首先，我们用两个 long long 的 dividend1, divisor1 来把传进来的参数转成绝对值，用 flag 记下符号，去掉负号方便后面的运算。

上面说了，既然不能一次次的减，那我们可以通过翻倍的方式来加速。第一次减 divisor1，商 quotient 加1，第二次减 divisor1 的两倍，不能用乘法，那么两倍就是 divisor1 += divisor1，相应的，商也要加 2，第三次 divisor1 再翻一倍，商加 4，以此类推……

每次计算，我们把都把当前的除数 divisor1 和倍数 times 存下来放到 vector 数组备用。

当循环结束之后，我们还没有得到最后的结果。因为我们的除数 divisor1是翻倍的，有可能在循环结束的时候，虽然被除数 dividend1 比当前的除数小，但是可能比原来的除数 divisor 大的，还需要接着计算。

我们再把剩下的被除数 dividend1依次和存下来的中间过程除数 divisor1进行计算，为了加快计算这个过程要从数组的后面开始，也就是divisor1 从大到小的顺序。

举个例子：dividend = 16, divisor = 3

循环体1

	dividend1	divisor1	times	quotient
初始值	16	3	1	0
第1次循环后	13	6	2	1
第2次循环后	7	12	4	3

这个时候，循环体1就结束了，这时候 dividend1 是 7，比 12 小，但是比 6 和 3 大，我们可继续执行循环体2

循环体2

	dividend1	divisor1(vec[i].first)	times(vec[i].second)	quotient
初始值	7	6	2	3
第1次循环后	1	3	1	5

至此整个计算就完成了，得到最终的商是 5。

我们通过 3 次循环得到了最终结果，比依次减的方法少了 2 次。被除数和除数的比值越大，这个算法的加速效果越明显。比如被除数是 2147483647，除数是 1，按照原始算法，要执行 2147483647 次循环，而我们的算法只要 31 次。

Divide Two Integers#

Solution#

Divide Two Integers

Solution