[leetcode]Divide Two Integers @ Python，,原题地址：https

[leetcode]Divide Two Integers @ Python，,原题地址：https

原题地址：https://oj.leetcode.com/problems/divide-two-integers/

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

解题思路：不许用乘、除和求余实现两数的相除。那就只能用加和减了。正常思路是被除数一个一个的减除数，直到剩下的数比除数小为止，就得到了结果。这样是无法ac的，因为时间复杂度为O(n)，比如一个很大的数除1，就很慢。这里我们可以用二分查找的思路，可以说又是二分查找的变种。

代码：

class Solution:    # @return an integer    def divide(self, dividend, divisor):        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):            if abs(dividend) < abs(divisor):                return 0        sum = 0; count = 0; res = 0        a = abs(dividend); b = abs(divisor)        while a >= b:            sum = b            count = 1            while sum + sum <= a:                sum += sum                count += count            a -= sum            res += count        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):            res = 0 - res        return res

[leetcode]Divide Two Integers @ Python,布布扣,bubuko.com

[leetcode]Divide Two Integers @ Python