0029._Divide_Two_Integers.md

29. Divide Two Integers

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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.

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

不能乘除，所以我们改用位运算，运用二分的思想，beats 100%

因为最坏的情况就是最大的数除以1，即2**31 / 1, 所以时间复杂度就是O(1)，如果assuming n is the number of bits， 那就是O(lgN)

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        positive = (dividend > 0) is (divisor > 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:
            tmp, cnt = divisor, 1
            while dividend >= tmp:
                tmp <<= 1
                cnt <<= 1
            dividend -= tmp >> 1
            res += cnt >> 1
        res = res if positive else -res
        if res >= 2**31 - 1:
            return 2**31 - 1
        elif res <= -(2**31):
            return -(2**31)
        else:
            return res

最后的六行可以写成一行

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        positive = (dividend > 0) is (divisor > 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:
            tmp, cnt = divisor, 1
            while dividend >= tmp:
                cnt <<= 1
                tmp <<= 1
            dividend -= tmp >> 1
            res += cnt >> 1
        res = res if positive else -res
        return min(max(-(2**31), res), 2**31-1)