描述:不使用 * / % 完成除法操作。O(n)复杂度会超时,需要O(lg(n))复杂度。
代码:
class Solution:
# @return an integer
def dividePositive(self, dividend, divisor):
if dividend < divisor:
return 0 sum = divisor
count = 1
while sum + sum < dividend:
sum += sum
count += count count += self.dividePositive(dividend - sum, divisor) return count def divide(self, dividend, divisor):
if dividend >= 0:
if divisor > 0:
return self.dividePositive(dividend, divisor)
else:
return 0 - self.dividePositive(dividend, 0 - divisor)
else:
if divisor > 0:
return 0 - self.dividePositive(0 - dividend, divisor)
else:
return self.dividePositive(0 - dividend, 0 - divisor)