LeetCode 029 — Divide Two Integers

请注意,本文编写于 160 天前,最后修改于 51 天前,其中某些信息可能已经过时。

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 longdividend1, 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

dividend1divisor1timesquotient
初始值16310
第1次循环后13621
第2次循环后71243

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

循环体2

dividend1divisor1
(vec[i].first)
times
(vec[i].second)
quotient
初始值7623
第1次循环后1315

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

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

添加新评论