首页 > 代码库 > #Leet Code# Divide Two Integers

#Leet Code# Divide Two Integers

描述:不使用 * / % 完成除法操作。O(n)复杂度会超时,需要O(lg(n))复杂度。

代码:

 1 class Solution: 2     # @return an integer 3     def dividePositive(self, dividend, divisor): 4         if dividend < divisor: 5             return 0 6  7         sum = divisor 8         count = 1 9         while sum + sum < dividend:10             sum += sum11             count += count12         13         count += self.dividePositive(dividend - sum, divisor)14         15         return count16 17     def divide(self, dividend, divisor):18         if dividend >= 0:19             if divisor > 0:20                 return self.dividePositive(dividend, divisor)21             else:22                 return 0 - self.dividePositive(dividend, 0 - divisor)23         else:24             if divisor > 0:25                 return 0 - self.dividePositive(0 - dividend, divisor)26             else:27                 return self.dividePositive(0 - dividend, 0 - divisor)