Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目链接：https://leetcode.com/problems/divide-two-integers/?tab=Description

提示

不能用乘除和取模，首先想到得减法， 但是减法会超时，我们可以采用指数衰减得减法。 b(1+21+22+…)+c = a

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0)
        a, b = abs(dividend), abs(divisor)
        ret, c = 0, 0
        while a >= b:
            c = b
            i = 0
            while a >= c:
                a -= c
                ret += (1 << i)
                i += 1
                c <<= 1
        if sign:
            ret = -ret
        return min(max(-2147483648, ret), 2147483647)


s = Solution()
print(s.divide(5, 2))