记录学习心得
看了几遍总觉得这题很难懂,借鉴大佬题解读懂,善用long
类型,利用贪心和倍增思想
大佬题解:https://www.acwing.com/solution/content/14434/
算法
(倍增+贪心)$O(logb)$
我们用减法模拟除法时,减去被除数的个数即为最后的要求的商,而这个方法在被除数很大,除数很小时,时间复杂度会非常高。比如被除数和除数范围均在$[−2^31,2^31−1][−2^31,2^31−1]$中,当被除数取最大,除数为1时,结果会约等于$2^31$,如果选择每次减1,则最终时间复杂度会达到上亿级,因此我们需要对算法进行优化。
倍增
我们在减法时,一个个减很慢,可以每次减去一个更大的数来加速。具体方法为,每次减去一个不大于被除数的除数的倍数,同时纪录倍增了几次即为答案。
贪心
利用贪心思想,每次减去的数越大,总的运算次数越少,故而每次需要求出该次运算中,不大于被除数的除数的最大倍数值,同时答案加上该倍数,直到被除数小于除数
特判:溢出情况+使用
long
类型变量
C++代码
class Solution {
public:
int divide(int x, int y) {
// 特判:如果除法溢出,返回2 ^ 31 - 1;只有这种情况ans会溢出
if (x == INT_MIN && y == -1) return INT_MAX;
long a = abs(x), b = abs(y), ans = 0;
int sign = x < 0 ^ y < 0 ? -1 : 1;
while (a >= b) { // 保证被除数>=除数,ans起码有1
long tmp = b, m = 1;
while (tmp << 1 <= a) { // 找到最大的小于被除数的除数倍数值
tmp <<= 1; // 除数倍增
m <<= 1; // 减法次数倍增---答案
}
a -= tmp; // 被除数减小
ans += m; // 答案增加
}
ans *= sign;
return ans;
}
};