29.divide-two-integers.md

题目地址(29. 两数相除)

https://leetcode-cn.com/problems/divide-two-integers/

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2   示例 1: 输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 示例 2: 输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2   提示： 被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 

前置知识

• 二分法

公司

• Facebook
• Microsoft
• Oracle

思路

符合直觉的做法是，减数一次一次减去被减数，不断更新差，直到差小于 0，我们减了多少次，结果就是多少。

核心代码：

letacc=divisor;letcount=0;while(dividend-acc>=0){acc+=divisor;count++;}returncount;

这种做法简单直观，但是性能却比较差. 下面来介绍一种性能更好的方法。

通过上面这样的分析，我们直到可以使用二分法来解决，性能有很大的提升。

关键点解析

• 二分查找

• 正负数的判断中，这样判断更简单。

constisNegative=dividend>0!==divisor>0;

或者利用异或：

constisNegative=dividend^(divisor<0);

代码

• 语言支持：JS, Python3, CPP

/* * @lc app=leetcode id=29 lang=javascript * * [29] Divide Two Integers *//** * @param {number} dividend * @param {number} divisor * @return {number} */vardivide=function(dividend,divisor){if(divisor===1)returndividend;// 这种方法很巧妙，即符号相同则为正，不同则为负constisNegative=dividend>0!==divisor>0;constMAX_INTERGER=Math.pow(2,31);constres=helper(Math.abs(dividend),Math.abs(divisor));// overflowif(res>MAX_INTERGER-1||res<-1*MAX_INTERGER){returnMAX_INTERGER-1;}returnisNegative ? -1*res : res;};functionhelper(dividend,divisor){// 二分法if(dividend<=0)return0;if(dividend<divisor)return0;if(divisor===1)returndividend;letacc=2*divisor;letcount=1;while(dividend-acc>0){acc+=acc;count+=count;}// 直接使用位移运算，比如acc >> 1会有问题constlast=dividend-Math.floor(acc/2);returncount+helper(last,divisor);}

Python3 Code:

classSolution: defdivide(self, dividend: int, divisor: int) ->int: """ 二分法 :param int divisor :param int dividend :return int """# 错误处理ifdivisor==0: raiseZeroDivisionErrorifabs(divisor) ==1: result=dividendif1==divisorelse-dividendreturnmin(2**31-1, max(-2**31, result)) # 确定结果的符号sign= ((dividend>=0) == (divisor>=0)) result=0# abs也可以直接写在while条件中，不过可能会多计算几次_divisor=abs(divisor) _dividend=abs(dividend) while_divisor<=_dividend: r, _dividend=self._multi_divide(_divisor, _dividend) result+=rresult=resultifsignelse-result# 注意返回值不能超过32位有符号数的表示范围returnmin(2**31-1, max(-2**31, result)) def_multi_divide(self, divisor, dividend): """ 翻倍除法，如果可以被除，则下一步除数翻倍，直至除数大于被除数， 返回商加总的结果与被除数的剩余值； 这里就不做异常处理了； :param int divisor :param int dividend :return tuple result, left_dividend """result=0times_count=1whiledivisor<=dividend: dividend-=divisorresult+=times_counttimes_count+=times_countdivisor+=divisorreturnresult, dividend

CPP Code:

classSolution { public:intdivide(int dividend, int divisor) { if (!divisor) return0; // divide-by-zero errorbool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2); if (pos1) dividend = -dividend; if (pos2) divisor = -divisor; int q = 0, d = divisor, t = 1; while (t > 0 && dividend < 0) { if (dividend - d <= 0) { dividend -= d; q -= t; if ((INT_MIN >> 1) < d) { t <<= 1; d <<= 1; } } else { d >>= 1; t >>= 1; } } return pos? -q : q; } };

复杂度分析

• 时间复杂度：$O(logN)$
• 空间复杂度：$O(1)$

相关题目

• 875.koko-eating-bananas

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。