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

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 次。