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 32 3 2 位有符号整数,存在溢出的可能,所以我们首先进行类型转换,转换成 Long \textit{Long} 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 32 3 2 位整数”,所以代码中都不能使用任何 64 64 6 4 位整数。
如果除法结果溢出,那么我们需要返回 2 31 − 1 2^{31}-1 2 3 1 − 1 作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论:
当被除数为 32 32 3 2 位有符号整数的最小值 − 2 31 -2^{31} − 2 3 1 时:
如果除数为 1 1 1 ,那么我们可以直接返回答案 − 2 31 -2^{31} − 2 3 1 ;
如果除数为 − 1 -1 − 1 ,那么答案为 2 31 2^{31} 2 3 1 ,产生了溢出。此时我们需要返回 2 31 − 1 2^{31}-1 2 3 1 − 1 。
当除数为 32 32 3 2 位有符号整数的最小值 − 2 31 -2^{31} − 2 3 1 时:
如果被除数同样为 − 2 31 -2^{31} − 2 3 1 ,那么我们可以直接返回答案 1 1 1 ;
对于其余的情况,我们返回答案 0 0 0 。
当被除数为 0 0 0 时,我们可以直接返回答案 0 0 0 。
对于一般的情况,根据除数和被除数的符号,我们需要考虑 4 4 4 种不同的可能性。因此,为了方便编码,我们可以将被除数或者除数取相反数,使得它们符号相同。
如果我们将被除数和除数都变为正数,那么可能会导致溢出。例如当被除数为 − 2 31 -2^{31} − 2 3 1 时,它的相反数 2 31 2^{31} 2 3 1 产生了溢出。因此,我们可以考虑将被除数和除数都变为负数,这样就不会有溢出的问题,在编码时只需要考虑 1 1 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 \texttt{quickMul} quickMul 的 quickAdd \texttt{quickAdd} quickAdd 方法。
不考虑溢出情况,设被除数为 X X X ,除数为 Y Y Y ,X > 0 Y > 0 X \gt 0 Y \gt 0 X > 0 Y > 0 ,那么结果 Z = X / Y , 0 ≤ Z ≤ X Z = X/Y, 0 \le Z \le X Z = X / Y , 0 ≤ Z ≤ X 。
根据除法以及余数的定义,我们可以将其改成乘法的等价形式,即:
Z × Y ≤ X < ( Z + 1 ) × Y Z \times Y \le X < (Z+1) \times Y
Z × Y ≤ X < ( Z + 1 ) × Y
因此可以使用二分查找 在 [ 0 , X ] [0, X] [ 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 32 3 2 位整数,所以我们需要将 X X X 和 Y Y Y 转换成负数 进行处理,和之前公式不同的是:
Z × Y ≥ X > ( Z + 1 ) × Y , 0 ≤ Z < X Z \times Y \ge X > (Z+1) \times Y, 0 \le Z < X
Z × Y ≥ X > ( Z + 1 ) × Y , 0 ≤ Z < X
使用二分查找 找到最大的 Z Z Z 使得 Z × Y ≥ X Z \times Y \geq X Z × Y ≥ X 成立。
细节
二分查找的下界为 0 0 0 ,上界为 2 31 − 1 2^{31} - 1 2 3 1 − 1 。唯一可能出现的答案为 2 31 2^{31} 2 3 1 的情况已经进行了特殊处理,因此答案的最大值为 2 31 − 1 2^{31} - 1 2 3 1 − 1 。如果二分查找失败,那么答案一定为 0 0 0 。
较大的 Z Z Z 也会导致加法运算溢出。例如要判断 A + B A + B A + B 是否小于 C C C 时(其中 A , B , C A, B, C A , B , C 均为负数),A + B A + B A + B 可能会产生溢出,因此必须将判断改为 A < C − B A < C - B A < C − B 是否成立。由于任意两个负数的差一定在 [ − 2 31 + 1 , 2 31 − 1 ] [-2^{31} + 1, 2^{31} - 1] [ − 2 3 1 + 1 , 2 3 1 − 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 . 😉😃💗