给定两个整数,被除数 dividend
和除数 divisor
。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend
除以除数 divisor
得到的商。
整数除法的结果应当截去(truncate
)其小数部分,例如:truncate(8.345) = 8
以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示:
由于题目限定了我们不能使用乘法、除法和 mod 运算符。
我们可以先实现一个「倍增乘法」,然后利用对于 x
除以 y
,结果 x / y
必然落在范围 [0, x]
的规律进行二分:
class Solution {
public int divide(int a, int b) {long x = a, y = b;
boolean isNeg = false;
if ((x > 0 && y < 0) || (x < 0 && y > 0)) isNeg = true;
if (x < 0) x = -x;
if (y < 0) y = -y;
long l = 0, r = x;
while (l < r) {
long mid = l + r + 1 >> 1;
if (mul(mid, y) <= x) {
l = mid;
} else {
r = mid - 1;
}
}
long ans = isNeg ? -l : l;
if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE;
return (int)ans;
}
long mul(long a, long k) {
long ans = 0;
while (k > 0) {
if ((k & 1) == 1) ans += a;
k >>= 1;
a += a;
}
return ans;
}
}
x
采用的是二分策略。复杂度为这道题的解法,主要涉及的模板有两个。
一个是「二分」模板,一个是「快速乘法」模板。都是高频使用的模板。
其中「二分」模板其实有两套,主要是根据 check(mid)
函数为 true
时,需要调整的是 l
指针还是 r
指针来判断。
check(mid) == true
调整的是 l
时:计算 mid
的方式应该为 mid = l + r + 1 >> 1
:long l = 0, r = 1000009;
while (l < r) {
long mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
check(mid) == true
调整的是 r
时:计算 mid
的方式应该为 mid = l + r >> 1
:long l = 0, r = 1000009;
while (l < r) {
long mid = l + r >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
另外一个是「快速乘法」模板,采用了倍增的思想:
long mul(long a, long k) {
long ans = 0;
while (k > 0) {
if ((k & 1) == 1) ans += a;
k >>= 1;
a += a;
}
return ans;
}
这是我们「刷穿 LeetCode」系列文章的第 No.29
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 29/1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。