LeetCode 29. 两数相除 — Python3 实现核心思路倍增法位移模拟题目限制不能使用*、/、%因此我们通过除数的不断翻倍来逼近被除数类似于手动做长除法的原理。classSolution:defdivide(self,dividend:int,divisor:int)-int:INT_MAX2**31-1# 2147483647INT_MIN-2**31# -2147483648# 唯一会溢出的情况-2^31 / -1 2^31超出 32 位有符号整数范围ifdividendINT_MINanddivisor-1:returnINT_MAX# 判断结果符号两数符号不同则为负negative(dividend0)!(divisor0)# 取绝对值处理Python 整数不会溢出无需像 Rust/Java 那样转 longdvdabs(dividend)dvsabs(divisor)result0whiledvddvs:tempdvs multiple1# 内层循环除数不断左移翻倍×2直到超过被除数# temp 1 等价于 temp * 2但符合题目不用乘法的要求whiledvd(temp1):temp1multiple1# 减去已逼近的值并累加对应的商dvd-temp resultmultiple# 还原符号ifnegative:result-result# 截断到 32 位有符号整数范围虽然 Python 不会溢出但题目要求returnmax(INT_MIN,min(INT_MAX,result))执行流程图解以divide(10, 3)为例轮次 dvd剩余 temp当前除数倍数 multiple当前商倍数 result累计商初始 10 — — 0第1轮 10 → 1 3 → 6 → 12停→ 回退到 6 1 → 2 → 4停→ 回退到 2 0 2 2第2轮 1 3 1内层不执行 1 2 0 2循环结束最终dvd 1即余数result 3。复杂度分析指标 复杂度 说明时间 O(log²N) 外层循环 O(log N)内层倍增 O(log N)空间 O(1) 仅使用常数变量关键细节符号判断(dividend 0) ! (divisor 0)比写四个分支更简洁异号为True结果为负。为什么用temp 1而不是temp * 2题目明确禁止乘法运算符*但位运算是允许的这是此类题目的标准做法。Python 不需要处理abs(INT_MIN)溢出在 Rust/Java/C 中abs(-2^31)会溢出必须转 64 位整数。Python 的int精度无上限直接abs()即可。最后的max/min截断虽然 Python 不会溢出但题目要求返回 32 位有符号整数最后做一次范围截断确保合规。