29. 兩數相除

• 2019 年 10 月 7 日
• 筆記

題目描述

給定兩個整數，被除數 dividend 和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。

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

示例 1:

輸入: dividend = 10, divisor = 3  輸出: 3

示例 2:

輸入: dividend = 7, divisor = -3  輸出: -2

說明:

被除數和除數均為 32 位有符號整數。除數不為 0。假設我們的環境只能存儲 32 位有符號整數，其數值範圍是 [−231, 231 − 1]。本題中，如果除法結果溢出，則返回 231 − 1。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/divide-two-integers 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

思路

符合直覺的做法是，減數一次一次減去被減數，不斷更新差，直到差小於0，我們減了多少次，結果就是多少。

核心程式碼：

let acc = divisor;    let count = 0;      while (dividend - acc >= 0) {      acc += divisor;      count++;    }      return count;

這種做法簡單直觀，但是性能卻比較差. 下面來介紹一種性能更好的方法。

通過上面這樣的分析，我們直到可以使用二分法來解決，性能有很大的提升。

關鍵點解析

• 二分查找
• 正負數的判斷中，這樣判斷更簡單。

const isNegative = dividend > 0 !== divisor > 0;

程式碼

/*   * @lc app=leetcode id=29 lang=javascript   *   * [29] Divide Two Integers   */  /**   * @param {number} dividend   * @param {number} divisor   * @return {number}   */  var divide = function(dividend, divisor) {    if (divisor === 1) return dividend;      // 這種方法很巧妙，即符號相同則為正，不同則為負    const isNegative = dividend > 0 !== divisor > 0;      const MAX_INTERGER = Math.pow(2, 31);      const res = helper(Math.abs(dividend), Math.abs(divisor));      // overflow    if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {      return MAX_INTERGER - 1;    }      return isNegative ? -1 * res : res;  };    function helper(dividend, divisor) {    // 二分法    if (dividend <= 0) return 0;    if (dividend < divisor) return 0;    if (divisor === 1) return dividend;      let acc = 2 * divisor;    let count = 1;      while (dividend - acc > 0) {      acc += acc;      count += count;    }    // 直接使用位移運算，比如acc >> 1會有問題    const last = dividend - Math.floor(acc / 2);      return count + helper(last, divisor);  }

相關題目

• 875.koko-eating-bananas