[Leetcode][29. 两数相除] 3种方法:暴力法,二分搜索,递归
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
2229. 两数相除
给定两个整数,被除数`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\) 位有符号整数,存在溢出的可能,所以我们首先进行类型转换,转换成 \(\textit{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
30public 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
44public 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\) 位整数。
如果除法结果溢出,那么我们需要返回 \(2^{31}-1\) 作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论:
- 当被除数为 \(32\) 位有符号整数的最小值 \(-2^{31}\) 时:
- 如果除数为 \(1\),那么我们可以直接返回答案 \(-2^{31}\);
- 如果除数为 \(-1\),那么答案为 \(2^{31}\),产生了溢出。此时我们需要返回 \(2^{31}-1\)。
- 当除数为 \(32\) 位有符号整数的最小值 \(-2^{31}\) 时:
- 如果被除数同样为 \(-2^{31}\),那么我们可以直接返回答案 \(1\);
- 对于其余的情况,我们返回答案 \(0\)。
- 当被除数为 \(0\) 时,我们可以直接返回答案 \(0\)。