class Solution {
public:
int divide(int a, int b) {
}
};
剑指 Offer II 001. 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：
truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2[−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
示例 1：
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：
输入：a = 7, b = -3 输出：-2 解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
输入：a = 0, b = 1
输出：0
示例 4：
输入：a = 1, b = 1
输出：1
提示:
-231 <= a, b <= 231 - 1b != 0
注意：本题与主站 29 题相同：https://leetcode.cn/problems/divide-two-integers/
原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 14.8 MB, 提交时间: 2022-08-12 11:41:33
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