Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero.
Example 1: Input: dividend = 10, divisor = 3 Output: 3
Example 2: Input: dividend = 7, divisor = -3 Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
思路
在题中明确了不能使用乘法和除法以及模运算,所以我们只能通过其他办法来进行解决。除法解决的问题就是看被除数里面有多少个除数的问题,最简单的方法就是我们可以使用减法,对被除数减去除数,然后计数加一。但是这种办法当从被除数较大时时间复杂度较高,因此我们可以对其进行改进,对被除数从除数的倍数开始减去,然后每次相减完毕之后对对除数进行加倍。这样当被除数比较大时,也能很快的相减完毕。
解决代码
class Solution(object):
def divide(self, dividend, divisor):
positive = (dividend < 0) is (divisor < 0) # 被除数和除数为负数的情况进行考虑。
dividend, divisor = abs(dividend), abs(divisor) # 对其取绝对值
res = 0 # 结果
while dividend >= divisor: # 当被除数小于当前除数时,说明已经不能被整除了。
tem, i = divisor, 1 # 存储倍数和除数
while dividend >= tem: # 当被除数小于当前倍数除数时,终止循环
dividend -= tem # 被除数减去除数
res += i # 结果加上相应的倍数
i <<= 1 # 除数的倍数
tem <<= 1 # 除数翻倍
if not positive: # 判断是否有负数
res = -res
return min(max(-2147483648, res), 2147483647) # 超出范围判断