内容简介：题目要求不用乘法、除法和取模运算符，实现整型除法运算。既然不能用乘法和除法运算符，那么基本思路就是用减法来代替。不过如果用每次循环减一次被除数这种方式，是肯定会超时的。所以要想办法加速运算。
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 次。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
