class Solution {
public:
int divide(int dividend, int divisor) {
}
};
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
提示：
原站题解
python3 解法, 执行用时: 52 ms, 内存消耗: 14.8 MB, 提交时间: 2022-08-12 11:41:02
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MIN, INT_MAX = -2**31, 2**31 - 1
# 考虑被除数为最小值的情况
if dividend == INT_MIN:
if divisor == 1:
return INT_MIN
if divisor == -1:
return INT_MAX
# 考虑除数为最小值的情况
if divisor == INT_MIN:
return 1 if dividend == INT_MIN else 0
# 考虑被除数为 0 的情况
if dividend == 0:
return 0
# 一般情况，使用类二分查找
# 将所有的正数取相反数，这样就只需要考虑一种情况
rev = False
if dividend > 0:
dividend = -dividend
rev = not rev
if divisor > 0:
divisor = -divisor
rev = not rev
candidates = [divisor]
# 注意溢出
while candidates[-1] >= dividend - candidates[-1]:
candidates.append(candidates[-1] + candidates[-1])
ans = 0
for i in range(len(candidates) - 1, -1, -1):
if candidates[i] >= dividend:
ans += (1 << i)
dividend -= candidates[i]
return -ans if rev else ans
python3 解法, 执行用时: 52 ms, 内存消耗: 14.9 MB, 提交时间: 2022-08-12 11:40:35
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MIN, INT_MAX = -2**31, 2**31 - 1
# 考虑被除数为最小值的情况
if dividend == INT_MIN:
if divisor == 1:
return INT_MIN
if divisor == -1:
return INT_MAX
# 考虑除数为最小值的情况
if divisor == INT_MIN:
return 1 if dividend == INT_MIN else 0
# 考虑被除数为 0 的情况
if dividend == 0:
return 0
# 一般情况，使用二分查找
# 将所有的正数取相反数，这样就只需要考虑一种情况
rev = False
if dividend > 0:
dividend = -dividend
rev = not rev
if divisor > 0:
divisor = -divisor
rev = not rev
# 快速乘
def quickAdd(y: int, z: int, x: int) -> bool:
# x 和 y 是负数，z 是正数
# 需要判断 z * y >= x 是否成立
result, add = 0, y
while z > 0:
if (z & 1) == 1:
# 需要保证 result + add >= x
if result < x - add:
return False
result += add
if z != 1:
# 需要保证 add + add >= x
if add < x - add:
return False
add += add
# 不能使用除法
z >>= 1
return True
left, right, ans = 1, INT_MAX, 0
while left <= right:
# 注意溢出，并且不能使用除法
mid = left + ((right - left) >> 1)
check = quickAdd(divisor, mid, dividend)
if check:
ans = mid
# 注意溢出
if mid == INT_MAX:
break
left = mid + 1
else:
right = mid - 1
return -ans if rev else ans
java 解法, 执行用时: 1 ms, 内存消耗: 38.7 MB, 提交时间: 2022-08-12 11:39:40
// 100/3
// 100>3 100>6 100>12 100>24 100>48 100>96 100<192 ---- 使用了 2^5 = 32 个3，还剩 100 - 96 = 4 需要被除
// 4>3 4<6 ---- 使用了 2^0 = 1 个3，还剩 4 - 3 = 1 需要被除
// 1<3 ---- 被除数小于除数，递归结束，总计使用了 33 个 3
class Solution {
public int divide(int dividend, int divisor) {
// 当除数为1，直接返回被除数
if (divisor == 1) {
return dividend;
}
// 当除数为-1且被除数为Integer.MIN_VALUE时，将会溢出，返回Integer.MAX_VALUE
if (divisor == -1 && dividend == Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}
// 把被除数与除数调整为正数,为防止被除数Integer.MIN_VALUE转换为正数会溢出，使用long类型保存参数
if (dividend < 0 && divisor < 0) {
return divide(-(long) dividend, -(long) divisor);
} else if (dividend < 0 || divisor < 0) {
return -divide(Math.abs((long) dividend), Math.abs((long) divisor));
} else {
return divide((long) dividend, (long) divisor);
}
}
public int divide(long dividend, long divisor) {
// 如果被除数小于除数，结果明显为0
if (dividend < divisor) {
return 0;
}
long sum = divisor; // 记录用了count个divisor的和
int count = 1; // 使用了多少个divisor
while (dividend >= sum) {
// 每次翻倍
sum <<= 1;
count <<= 1;
}
// 此时dividend < sum
sum >>>= 1;
count >>>= 1;
// 此时dividend >= sum
// 将count个divisor从dividend消耗掉，剩下的还需要多少个divisor交由递归函数处理
return count + divide(dividend - sum, divisor);
}
}