TNotes.leetcode

Appearance

0029. 两数相除【中等】

0029. 两数相除【中等】 ​

1. 📝 题目描述 ​

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8，-2.7335 将被截断至 -2。

返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,231−1]。本题中，如果商严格大于 231−1，则返回 231−1；如果商严格小于 −231，则返回 −231。

示例 1：

txt
输入：dividend = 10, divisor = 3
输出：3

解释：10/3 = 3.33333..，向零截断后得到 3。

示例 2：

txt
输入：dividend = 7, divisor = -3
输出：-2

解释：7/-3 = -2.33333..，向零截断后得到 -2。

提示：

  • -2^31 <= dividend, divisor <= 2^31 - 1
  • divisor != 0

2. 🎯 s.1 - 倍增就大法（位移加速减法） ​

c
int divide(int dividend, int divisor) {
    // 唯一溢出情况：-2^31 / -1 = 2^31 超出 INT_MAX
    if (dividend == INT_MIN && divisor == -1)
        return INT_MAX;

    int sign = (dividend > 0) == (divisor > 0) ? 1 : -1;
    // 全转为负数操作，避免 -2^31 取绝对値溢出
    long long a = dividend > 0 ? -(long long)dividend : (long long)dividend;
    long long b = divisor > 0 ? -(long long)divisor : (long long)divisor;
    long long ans = 0;

    while (a <= b) {
        long long temp = b;
        long long cnt = 1;
        // 倍增加速：只要当前 temp 再翻倍后仍然 >= a，就继续翻倍
        while (a - temp <= temp) {
            temp += temp; // 不能用 temp <<= 1，因为 temp 为负数，负数左移是 C
                          // 语言标准中的未定义行为
            cnt += cnt;
        }
        a -= temp;
        ans += cnt;
    }

    return sign == 1 ? (int)ans : (int)-ans;
}
js
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  const INT_MAX = 2 ** 31 - 1
  const INT_MIN = -(2 ** 31)

  // 唯一溢出情况：-2^31 / -1 = 2^31
  if (dividend === INT_MIN && divisor === -1) return INT_MAX

  const sign = dividend > 0 === divisor > 0 ? 1 : -1
  // 全转为负数操作，避免 -2^31 取绝对値溢出
  let a = -Math.abs(dividend)
  let b = -Math.abs(divisor)
  let ans = 0

  while (a <= b) {
    let temp = b
    let cnt = 1
    while (a - temp <= temp) {
      // 不能用 <<= 做倍增，因为 JS 位运算会先把 Number 转成 32 位有符号整数
      // 一旦结果超过 32 位范围，高位会被截断，temp 和 cnt 都可能发生符号翻转
      // 例如 cnt = 1073741824 时，32 位二进制是 01000000 00000000 00000000 00000000
      // 再左移一次会变成 10000000 00000000 00000000 00000000，也就是 -2147483648
      // 这里改用加法倍增，整个计算过程都保持在 Number 的安全整数范围内
      temp += temp
      cnt += cnt
    }
    a -= temp
    ans += cnt
  }

  return sign === 1 ? ans : -ans
}
py
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -(2**31)

        # 唯一溢出情况：-2^31 / -1 = 2^31
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

        sign = 1 if (dividend > 0) == (divisor > 0) else -1
        # 全转为负数操作，避免 -2^31 取绝对値溢出
        a = -abs(dividend)
        b = -abs(divisor)
        ans = 0

        while a <= b:
            temp, cnt = b, 1
            # 倍增加速：找到最大的 2^k 使得 temp*2^k >= a
            while a - temp <= temp:
                temp <<= 1
                cnt <<= 1
            a -= temp
            ans += cnt

        return ans if sign == 1 else -ans
  • 时间复杂度：O(log2⁡Q)，其中 Q=⌊|dividend||divisor|⌋，最坏情况下外层和内层循环都为 O(log⁡Q)
  • 空间复杂度：O(1)，只使用了常数级别的额外变量

算法思路：

  • 先单独处理唯一溢出情况：-2^31 / -1 结果超出 INT_MAX，直接返回 INT_MAX
  • 确定结果符号：同号为正，异号为负
  • 将被除数和除数统一转成负数：因为 32 位整数里负数范围比正数多 1 个，INT_MIN 的绝对值无法用正数表示，统一转负后能避开这个边界问题
  • 外层循环：每轮从除数 b 出发，同时维护当前倍增块 temp 和对应商 cnt
  • 内层循环结束后，temp 就是当前能减去的最大倍增块；将它从 a 中减掉，并把对应的 cnt 累加到答案
  • 重复直至被除数已小于除数，最后根据符号返回结果

Discussions