29. 两数相除 [medium]

https://leetcode-cn.com/problems/divide-two-integers/

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

通过次数52,409 | 提交次数262,680

Second Try

2020-07-02

这是看题解才了解的另一个写法。递归小函数div才是重点，虽然看起来很理所当然，但是还是花费了我许多时间，还是不够熟练。

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # 其实能够超出的只有divisor为0， 或者极小值翻转正值，也即dividend为极小值而divisor为-1的情况
        if divisor == 0 or (dividend == - 2 ** 31 and divisor == -1):
            return 2 ** 31 - 1
        if divisor == 1:  # 这个感觉可以加速不少
            return dividend
        # 还是可以都转换为正数来表达的
        swift = (dividend>0 and divisor <0) or (dividend < 0 and divisor > 0)
        dividend = dividend if dividend > 0 else -dividend
        divisor = divisor if divisor > 0 else -divisor
        # print(dividend, divisor)
        # 虽然很理所当然，当时写这个简单的递归小函数还是花费了我许多时间，还是不够熟练
        def div(dividend, divisor):
            if divisor > dividend:
                return 0
            i = 1
            t = divisor
            # 如果没有 2 * divisor < dividend的操作，dividend和divisor并不会被改变，还是一个个减的操作
            # 不管如何，操作后的dividend，总归是比当前的t要小的
            while t + t <= dividend:
                t += t
                i += i
            dividend -= t
            return i + div(dividend, divisor)
            
        quotient = div(dividend, divisor)
        return quotient if not swift else -quotient

执行用时：24 ms, 在所有 Python 提交中击败了93.84%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了20.00%的用户

First Try

2020-07-02

非常经典的翻倍方法，不过边角条件太多了，导致写得磕磕绊绊，编写代码耗时太长了。

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # 那就只能使用加法和减法了,但是一个一个加太慢了，估计还得用缓存？
        # 都改为正数好处理
        # 负数转正数可能溢出了，感觉得都改成负数吧。。
        if divisor == 0 or (dividend == -2**31 and divisor == -1):
            return 2 ** 31 - 1
        # 全部改成负数吧，比较容易处理溢出问题
        swift = False
        if dividend > 0:
            swift = True
            dividend = -dividend  
        if divisor > 0:
            if swift:
                swift = False
            else:
                swift = True
            divisor = -divisor
        cache = []
        i = 1
        pow_divisor = divisor
        while pow_divisor >= dividend:  # 都是负数
            cache.append([i, pow_divisor])
            i += i
            pow_divisor += pow_divisor # 每次翻倍，负数变得更小
        # print(cache)
        count = 0
        # print("ffff", dividend, divisor)
        while dividend <= divisor:
            for i, val in reversed(cache):
                if dividend <= val:
                    dividend -= val
                    count += i
                    # print(count)
            # print("wtf??", dividend, divisor, count)
            if dividend <= divisor:
                # print(dividend, count)
                dividend -= divisor
                count += 1
        # print(count, swift)
        return count if not swift else -count

执行用时：32 ms, 在所有 Python 提交中击败了67.93%
内存消耗：12.6 MB, 在所有 Python 提交中击败了20.00%的用户

time exceeded version

一点点的加法，直接就超时了，很正常。

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # 那就只能使用加法和减法了,但是一个一个加太慢了，估计还得用缓存？
        # 都改为正数好处理
        # 负数转正数可能溢出了，感觉得都改成负数吧。。
        if divisor == 0 or (dividend == -2**31 and divisor == 1):
            return 2 ** 31 - 1
        # 全部改成负数吧，比较容易处理溢出问题
        swift = False
        if dividend > 0:
            swift = True
            dividend = -dividend  
        if divisor > 0:
            if swift:
                swift = False
            else:
                swift = True
            divisor = -divisor
        count = 0
        # 应该会超时吧。。
        while dividend <= divisor:
            # print(dividend, count)
            dividend -= divisor
            count += 1
        # print(count, swift)
        return count if not swift else -count

29. 两数相除 [medium]​

Second Try​

First Try​

29. 两数相除 [medium]

Second Try

First Try