29. 两数相除
难度中等321收藏分享切换为英文关注反馈
给定两个整数，被除数 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 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
思路
这道题最初使的一步处理就是将
同号除法处理为绝对值相除的结果
异号除法处理为绝对值相除结果的相反数
由于除法是由减法叠加而来，所以，乍一看乍道题，直接循环减就完事了，结果不出意外的超时了。
果然这道题没有想象的那么简单。
考虑到超时的原因是循环次数过多，所以想要通过这道题就要减少循环次数，这里我马上就联想到了计算机网络中截断二进制指数退避算法，这道题可以用类似的方法，让每次做减法时不是直接去减divisor，而是减掉一个span，这个span的大小，初始值为divisor，随着程序迭代次数而不断翻倍，直到剩余的dividend < span ，这个时候将span归为初始值，然后在迭代的过程中继续增大。经过这样的简单处理之后便可以AC了。
- python代码
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
flag = False
if abs(dividend + divisor) == abs(dividend) + abs(divisor):
flag = True
dividend = abs(dividend)
divisor = abs(divisor)
res = 0
span ={
'size': divisor,
'count': 1
}
while divisor <= dividend:
if dividend < span['size']:
span['size'] = divisor
span['count'] = 1
dividend -= span['size']
res += span['count']
span['size'] += span['size']
span['count'] += span['count']
res = res if flag else -res
if res > 2 ** 31 - 1: return 2**31 - 1
elif res < -2 ** 31: return -2 ** 31
else: return res
执行结果：通过
执行用时 :28 ms, 在所有 Python3 提交中击败了98.75%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了7.69%的用户
除此之外，还有更直接的方法，即在刚开始减的时候，就先让span的大小指数增长到能接受的最大值，减掉之后剩余的部分再使用指数倍增剪掉最大值最后直到求得结果
这两种方法的时间复杂度是相似的
- python代码
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
flag = False
if abs(dividend + divisor) == abs(dividend) + abs(divisor):
flag = True
dividend = abs(dividend)
divisor = abs(divisor)
res = 0
while divisor <= dividend:
span = {
'size': divisor,
'count': 1
}
while span['size'] + span['size'] < dividend:
span['size'] += span['size']
span['count'] += span['count']
dividend -= span['size']
res += span['count']
res = res if flag else -res
if res > 2 ** 31 - 1: return 2**31 - 1
elif res < -2 ** 31: return -2 ** 31
else: return res
执行结果：通过
执行用时 :40 ms, 在所有 Python3 提交中击败了73.24%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了7.69%的用户
