📑 题目：29. 两数相除

🚀 本题 LeetCode 传送门

题目大意

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

说明:

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

解题思路

  • 给出除数和被除数，要求计算除法运算以后的商。注意值的取值范围在 [−2^31, 2^31 − 1] 之中。超过范围的都按边界计算。

  • 这一题可以用二分搜索来做。要求除法运算之后的商，把商作为要搜索的目标。商的取值范围是 [0, dividend]，所以从 0 到被除数之间搜索。利用二分，找到(商 + 1 ) 除数 > 被除数并且 商 除数 ≤ 被除数 或者 (商+1) 除数 ≥ 被除数并且商 除数 < 被除数的时候，就算找到了商，其余情况继续二分即可。最后还要注意符号和题目规定的 Int32 取值范围。

  • 二分的写法常写错的 3 点：

    1. low ≤ high (注意二分循环退出的条件是小于等于)
    2. mid = low + (high-low)»1 (防止溢出)
    3. low = mid + 1 ; high = mid - 1 (注意更新 low 和 high 的值，如果更新不对就会死循环)

代码

  1. package leetcode
  3. import (
  4.  ""math""
  5. )
  7. // 解法一 递归版的二分搜索
  8. func divide(dividend int, divisor int) int {
  9.  sign, res := -1, 0
  10.  // low, high := 0, abs(dividend)
  11.  if dividend == 0 {
  12.   return 0
  13.  }
  14.  if divisor == 1 {
  15.   return dividend
  16.  }
  17.  if dividend == math.MinInt32 && divisor == -1 {
  18.   return math.MaxInt32
  19.  }
  20.  if dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0 {
  21.   sign = 1
  22.  }
  23.  if dividend > math.MaxInt32 {
  24.   dividend = math.MaxInt32
  25.  }
  26.  // 如果把递归改成非递归，可以改成下面这段代码
  27.  // for low <= high {
  28.  //  quotient := low + (high-low)>>1
  29.  //  if ((quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) <= abs(dividend)) || ((quotient+1)*abs(divisor) >= abs(dividend) && quotient*abs(divisor) < abs(dividend)) {
  30.  //   if (quotient+1)*abs(divisor) == abs(dividend) {
  31.  //    res = quotient + 1
  32.  //    break
  33.  //   }
  34.  //   res = quotient
  35.  //   break
  36.  //  }
  37.  //  if (quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) > abs(dividend) {
  38.  //   high = quotient - 1
  39.  //  }
  40.  //  if (quotient+1)*abs(divisor) < abs(dividend) && quotient*abs(divisor) < abs(dividend) {
  41.  //   low = quotient + 1
  42.  //  }
  43.  // }
  44.  res = binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))
  45.  if res > math.MaxInt32 {
  46.   return sign * math.MaxInt32
  47.  }
  48.  if res < math.MinInt32 {
  49.   return sign * math.MinInt32
  50.  }
  51.  return sign * res
  52. }
  54. func binarySearchQuotient(low, high, val, dividend int) int {
  55.  quotient := low + (high-low)>>1
  56.  if ((quotient+1)*val > dividend && quotient*val <= dividend) || ((quotient+1)*val >= dividend && quotient*val < dividend) {
  57.   if (quotient+1)*val == dividend {
  58.    return quotient + 1
  59.   }
  60.   return quotient
  61.  }
  62.  if (quotient+1)*val > dividend && quotient*val > dividend {
  63.   return binarySearchQuotient(low, quotient-1, val, dividend)
  64.  }
  65.  if (quotient+1)*val < dividend && quotient*val < dividend {
  66.   return binarySearchQuotient(quotient+1, high, val, dividend)
  67.  }
  68.  return 0
  69. }
  71. // 解法二 非递归版的二分搜索
  72. func divide1(divided int, divisor int) int {
  73.  if divided == math.MinInt32 && divisor == -1 {
  74.   return math.MaxInt32
  75.  }
  76.  result := 0
  77.  sign := -1
  78.  if divided > 0 && divisor > 0 || divided < 0 && divisor < 0 {
  79.   sign = 1
  80.  }
  81.  dvd, dvs := abs(divided), abs(divisor)
  82.  for dvd >= dvs {
  83.   temp := dvs
  84.   m := 1
  85.   for temp<<1 <= dvd {
  86.    temp <<= 1
  87.    m <<= 1
  88.   }
  89.   dvd -= temp
  90.   result += m
  91.  }
  92.  return sign * result
  93. }