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
