By Long Luo
Leetcode 29. 两数相除 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 29. 两数相除
给定两个整数,被除数`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 提示: 被除数和除数均为$32$位有符号整数。 除数不为$0$。 假设我们的环境只能存储 $32$ 位有符号整数,其数值范围是 [-2^31, 2^31-1]。本题中,如果除法结果溢出,则返回2^31-1。
|
方法一:暴力法
思路与算法:
因为题目要求不能使用乘法、除法和mod
运算符,那么首先想到的是只能使用加减法了。
因为除法就是看被除数能让多少个除数相加,因为被除数和除数均为 32 位有符号整数,存在溢出的可能,所以我们首先进行类型转换,转换成 Long 型进行处理。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| public int divide(int dividend, int divisor) { if (dividend == 0) { return 0; }
long dividendLong = dividend; long divisorLong = divisor;
boolean sign = false; if (dividendLong < 0 && divisorLong < 0) { dividendLong = -dividendLong; divisorLong = -divisorLong; } else if (dividendLong < 0 && divisorLong > 0) { sign = true; dividendLong = -dividendLong; } else if (dividendLong > 0 && divisorLong < 0) { sign = true; divisorLong = -divisorLong; }
long ans = 0; while (dividendLong >= divisorLong) { dividendLong -= divisorLong; ans++; }
ans = sign ? -ans : ans;
return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans; }
|
毫无疑问,超时了!
卡在了这个 -2147483648 1
测试用例上,那么我们针对这些边界值进行处理:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| public int divide(int dividend, int divisor) { if (divisor == Integer.MIN_VALUE) { return dividend == Integer.MIN_VALUE ? 1 : 0; } if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { return dividend; } else if (divisor == -1) { return Integer.MAX_VALUE; } } else if (dividend == Integer.MAX_VALUE) { if (divisor == 1) { return dividend; } else if (divisor == -1) { return -dividend; } }
long dividendLong = dividend; long divisorLong = divisor;
boolean sign = false; if (dividendLong < 0 && divisorLong < 0) { dividendLong = -dividendLong; divisorLong = -divisorLong; } else if (dividendLong < 0 && divisorLong > 0) { sign = true; dividendLong = -dividendLong; } else if (dividendLong > 0 && divisorLong < 0) { sign = true; divisorLong = -divisorLong; }
long ans = 0; while (dividendLong >= divisorLong) { dividendLong -= divisorLong; ans++; }
ans = sign ? -ans : ans;
return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans; }
|
因为针对性处理了,所以上述代码 AC 了!
因为题目规定了“只能存储 32 位整数”,所以代码中都不能使用任何 64 位整数。
如果除法结果溢出,那么我们需要返回 231−1 作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论:
- 当被除数为 32 位有符号整数的最小值 −231 时:
- 如果除数为 1,那么我们可以直接返回答案 −231;
- 如果除数为 −1,那么答案为 231,产生了溢出。此时我们需要返回 231−1。
- 当除数为 32 位有符号整数的最小值 −231 时:
- 如果被除数同样为 −231,那么我们可以直接返回答案 1;
- 对于其余的情况,我们返回答案 0。
- 当被除数为 0 时,我们可以直接返回答案 0。
对于一般的情况,根据除数和被除数的符号,我们需要考虑 4 种不同的可能性。因此,为了方便编码,我们可以将被除数或者除数取相反数,使得它们符号相同。
如果我们将被除数和除数都变为正数,那么可能会导致溢出。例如当被除数为 −231 时,它的相反数 231 产生了溢出。因此,我们可以考虑将被除数和除数都变为负数,这样就不会有溢出的问题,在编码时只需要考虑 1 种情况了。
如果我们将被除数和除数的其中(恰好)一个变为了正数,那么在返回答案之前,我们需要对答案也取相反数。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { return dividend; } else if (divisor == -1) { return Integer.MAX_VALUE; } else if (divisor == Integer.MIN_VALUE) { return 1; } } else if (dividend == Integer.MAX_VALUE) { if (divisor == 1) { return dividend; } else if (divisor == -1) { return -dividend; } }
int ans = 0; boolean sign = true; if (dividend > 0 && divisor > 0) { dividend = -dividend; sign = false; } else if (dividend > 0 && divisor < 0) { dividend = -dividend; divisor = -divisor; } else if (dividend < 0 && divisor < 0) { sign = false; divisor = -divisor; }
while (dividend + divisor <= 0) { dividend += divisor; ans++; }
return sign ? -ans : ans; }
|
注意需要增加对 -2147483648 -2147483648
测试用例进行特殊处理,否则会出现超时,因为 -2147483648
取反还是 -2147483648
,会出现死循环!
复杂度分析:
方法二:二分查找
思路与算法:
参考 Illustration of Fast Power Algorithm - Exponentiation by Squaring or Binary Exponentiation ,实现一个类似 quickMul 的 quickAdd 方法。
不考虑溢出情况,设被除数为 X,除数为 Y,X>0Y>0,那么结果 Z=X/Y,0≤Z≤X。
根据除法以及余数的定义,我们可以将其改成乘法的等价形式,即:
Z×Y≤X<(Z+1)×Y
因此可以使用二分查找在 [0,X] 中寻找答案,每次循环都可以排除一半。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| public int divide(int dividend, int divisor) { long x = dividend; long y = divisor;
boolean sign = false;
if ((x > 0 && y < 0) || (x < 0 && y > 0)) { sign = true; }
if (x < 0) { x = -x; }
if (y < 0) { y = -y; }
long left = 0; long right = x;
while (left < right) { long mid = (left + right + 1) >> 1; long result = quickAdd(y, mid); if (result <= x) { left = mid; } else { right = mid - 1; } }
long ans = sign ? -left : left; if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) { return Integer.MAX_VALUE; }
return (int) ans; }
public long quickAdd(long x, long y) { long ans = 0; while (y > 0) { if ((y & 0x01) == 1) { ans += x; }
x += x; y = y >> 1; }
return ans; }
|
上述代码是需要转换成 long
型进行处理,但题目要求只能使用 32 位整数,所以我们需要将 X 和 Y 转换成负数进行处理,和之前公式不同的是:
Z×Y≥X>(Z+1)×Y,0≤Z<X
使用二分查找找到最大的 Z 使得 Z×Y≥X 成立。
细节
-
二分查找的下界为 0,上界为 231−1。唯一可能出现的答案为 231 的情况已经进行了特殊处理,因此答案的最大值为 231−1。如果二分查找失败,那么答案一定为 0。
-
较大的 Z 也会导致加法运算溢出。例如要判断 A+B 是否小于 C 时(其中 A,B,C 均为负数),A+B 可能会产生溢出,因此必须将判断改为 A<C−B 是否成立。由于任意两个负数的差一定在 [−231+1,231−1] 范围内,这样就不会产生溢出。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| public int divide(int dividend, int divisor) { if (divisor == Integer.MIN_VALUE) { return dividend == Integer.MIN_VALUE ? 1 : 0; }
if (dividend == 0) { return 0; }
if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { return Integer.MIN_VALUE; } else if (divisor == -1) { return Integer.MAX_VALUE; } }
boolean sign = false; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = true; }
if (dividend > 0) { dividend = -dividend; }
if (divisor > 0) { divisor = -divisor; }
int MAX = Integer.MIN_VALUE >> 1; int ans = 0;
while (dividend <= divisor) { int temp = divisor; int step = -1;
while (temp >= MAX && step >= MAX && temp >= dividend - temp) { temp += temp; step += step; }
dividend -= temp; ans += step; }
return sign ? ans : -ans; }
|
复杂度分析:
方法三:递归
思路与算法:
细节
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| public int divide(int dividend, int divisor) { if (divisor == Integer.MIN_VALUE) { return dividend == Integer.MIN_VALUE ? 1 : 0; }
if (dividend == 0) { return 0; }
if (dividend == Integer.MIN_VALUE) { if (divisor == 1) { return Integer.MIN_VALUE; } else if (divisor == -1) { return Integer.MAX_VALUE; } }
long x = dividend; long y = divisor;
boolean sign = false; if ((x > 0 && y < 0) || (x < 0 && y > 0)) { sign = true; }
x = x > 0 ? x : -x; y = y > 0 ? y : -y;
long ans = div(x, y); if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) { return Integer.MAX_VALUE; }
return (int) (sign ? -ans : ans); }
public long div(long dividend, long divisor) { if (dividend < divisor) { return 0; }
long ans = 1; long temp = divisor;
while ((temp + temp) <= dividend) { ans = ans << 1; temp = temp << 1; }
return ans + div(dividend - temp, divisor); }
|
复杂度分析:
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗