难点在于处理不能用long解决溢出问题
思路1：“二进制”减法(没有满足越界要求)
不能用除法，最简单的思路就是被除数(dividend)不断地减除数(divisor)，直到减到剩余余数，相减的次数就是结果。该方法的问题就是时间复杂度太高，
- 二进制优化，首先找到最大的n使得 $divisor 2^n < dividend$，每次减去 $ divisor 2^n， divisor 2^{n-1} ，divisor 2^{n-2} ……$,直到减到 $ divisor $
- 实际上就是将原来的逐个减去，变为二进制减去（找商的二进制表示），由于任何数都能由二进制表示，所以该方法必定有解
- 我的实现方法越界无法规避，只能用Long
复杂度分析：
没有分析的必要，由于只有32位整数，二进制一共只需要移动32次，时间复杂度与空间复杂度均为O(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
| public int divide(int dividend, int divisor) {
long result = 0;
boolean isNegative = (dividend < 0 & divisor > 0) || (dividend > 0 & divisor < 0);
long temp = 1;
long denominator = (long)Math.abs((long)dividend);
long numerator = (long)Math.abs((long)divisor);
while(numerator << 1 <= denominator){
temp = temp << 1;
numerator = numerator << 1;
}
while(numerator >= Math.abs((long)divisor)){
if(denominator >= numerator){
denominator -= numerator;
if(isNegative)
result -= temp;
else
result += temp;
}
numerator = numerator >> 1;
temp = temp >> 1;
}
if(result > Integer.MAX_VALUE){
result = Integer.MAX_VALUE;
}
return (int)result;
}
|
思路2：条件约束+二分查找（答案的方法看得我头疼）