[Math]029 Divide Two Integers***

• 分类：Math

• 考察知识点：Math/分治

• 最优解时间复杂度：**O(logn) **

• 最优解空间复杂度：**O(logn) **

29. Divide Two Integers

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:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if dividend==0 or abs(dividend)<abs(divisor):
            return 0
        
        #处理符号
        sign=1
        if dividend<0:
            dividend=-dividend
            sign=-sign
        if divisor<0:
            divisor=-divisor
            sign=-sign
        
        quotient=self.do_divide(dividend,divisor)
            
        res=quotient*sign
        if res<-2**31:
            return -2**31
        elif res>2**31-1:
            return 2**31-1
        else:      
            return res
        
    def do_divide(self,dividend,divisor):
   
        if dividend<divisor:
            return 0
        sum_=divisor
        multiple=1
        while (sum_+sum_)<=dividend:
            sum_+=sum_
            multiple+=multiple
            
        return self.do_divide(dividend-sum_,divisor)+multiple

讨论：

1.这种题目主要有四个地方要想，正负号，越界，是否=0，正常情况
2.这是一道非常重要的题目，虽然出现的次数并不是特别多，但是思想十分重要
3.这个题的考点应该是个二分法，时间复杂度和空间复杂度都是O(longn)

加油鸭！