目录

AaronJny

诗酒繁华,书剑天涯。

leetcode题解第29题 Divide Two Integers (两数相除)

题目的大意如下:

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

简单来说,就是需要在不借助 python 内部的乘、除、去余运算的情况下,实现整数除法运算,并返回运算的商的。余数忽略。

且在此之外,还有几点额外说明:

  • 除数永远不会为 0。
  • 被除数和除数都是 32 位有符号整数。
  • 假设计算机只能存储 32 位有符号整数,所以你返回的结果应该在 [−2^{31}, 2^{31} − 1]范围内,否则就返回 2^{31} − 1

样例输入 1:

dividend = 10, divisor = 3

样例输出 1:

3

样例输入 2:

dividend = 7, divisor = -3

样例输出 2:

-2

如果不借助语言内置的乘除法,应该怎么做除法运算呢?

一个最简单的方法是——不停累加除数,直到它大于被除数为止。这时,累加的次数-1 就是商。

这个方法看起来很美好,但是当被除数很大,而除数很小时,按这个方法就需要计算非常多次,时间复杂度很高。最不理想的情况下,被除数为 2^{31}-1 ,除数为 1,就需要运算 2^{31} 次。完全没法使用。

有什么优化的方法吗?

当然是有的,还记得小学的时候我们是怎么计算除法的吗?摆竖式呀!

我们可以用程序来模拟摆竖式的过程,从被除数中一部分一部分地和除数进行运算,这样哪怕数字很大,我们也能很快得出结果。这样,我们就把整个除法,拆成了被除数中的一部分和除数的除法运算的组合,其中还涉及到余数、补位等操作。什么?你说这样不还是有除法吗?需要考虑的是,当前的除法计算次数已经大大缩减了,每一小步的除法我们完全可以使用第一种方法来实现。

假设我们把摆竖式的过程称为复杂除法,第一种方法称为简单除法。那么当最坏的情况下,被除数为 2^{31}-1 ,除数为 1, 2^{31}-1 = 2147483647 ,长度为 10,我们需要做 10 次复杂除法。而每次复杂除法,我们都需要做一次简单除法。由于在摆竖式的过程中,取出的被除数的一部分的长度和除数的长度一般是相同的(当不相同时:被除数长度小,则直接商零,不需要计算;被除数长度大,需要的更多计算次数可以由前者平衡。所以这两种情况不会影响总的计算次数),那么一次简单除法的累加次数就不会超过 10 次。进而总的运算次数不超过 100 次。这样,应该能较明显地比较两者的速度快慢了。

ok,原理讲完了,上代码实现一下吧:

class Solution:
    def simple_divide(self, dividend, divisor):
        """
        使用加减法模拟一次简单的除法
        :param dividend: 被除数
        :param divisor: 除数
        :return: int,int 商,余数
        """
        # 被除数是除数的几倍
        cnt = 0
        # 当前除数的累加值
        add = 0
        # 如果当前累加值+除数仍小于被除数
        while add + divisor <= dividend:
            # 就累加一次
            add += divisor
            # 把倍数计数器+1
            cnt += 1
        # 判断累加值是否和被除数相等,相等则余数为0
        if add == dividend:
            last = 0
        # 否则余数为被除数和累加值的差值
        else:
            last = dividend - add
        # 返回商和余数
        return cnt, last

    def divide(self, dividend: int, divisor: int) -> int:
        """
        在不使用乘法、除法和mod运算符的情况下,给定除数和被除数,返回商
        :param dividend:被除数
        :param divisor:除数
        :return:商
        """
        # 先对一些特殊情况进行处理
        # 如果被除数为0,结果就为0
        if dividend == 0:
            result = 0
        # 如果除数为1,结果就为被除数
        elif divisor == 1:
            result = dividend
        # 如果除数为-1,结果为被除数的负数形式
        elif divisor == -1:
            result = -dividend
        # 如果除数为2,则直接使用位运算
        elif divisor == 2:
            if dividend & 1:
                result = (dividend - 1) >> 1
            else:
                result = dividend >> 1
        # 否则,我们模拟一下除法
        else:
            # 判断被除数的正负
            flag1 = -1 if dividend < 0 else 1
            # 判断除数的正负
            flag2 = -1 if divisor < 0 else 1
            # 对除数和被除数都保留其绝对值
            divisor = abs(divisor)
            dividend = abs(dividend)
            # 如果除数比被除数大,商就是0
            if dividend < divisor:
                result = 0
            # 否则,开始模拟计算
            else:
                quotients = []
                # 将被除数转成字符串,方便我们按位进行处理
                dividend_str = str(dividend)
                # 除数也做相同处理
                divisor_str = str(divisor)
                # 下面,我们开始摆竖式,计算除法
                # 从被除数开头的位置,取和除数相同位数的字符串
                last_str = dividend_str[:len(divisor_str)]
                # 被除数处理到那个位置了
                dividend_pos = len(divisor_str) - 1
                # 一步步计算竖式,知道算到最后一位
                while dividend_pos < len(dividend_str):
                    # 将我们取出的被除数部分转成证书
                    last = int(last_str)
                    # 如果这部分被除数比除数大
                    if last >= divisor:
                        # 就模拟一次简单的除法,计算商和余数
                        quo, las = self.simple_divide(last, divisor)
                        # 将这一步的商加入到列表中
                        quotients.append(str(quo))
                        # 把余数转成字符串,准备进行补位,算下一步
                        last_str = str(las)
                    # 否则的话,这部分商为0,这部分被除数都是余数
                    else:
                        quotients.append('0')
                    # 被除数的游标后移以为
                    dividend_pos += 1
                    # 如果没有算到最后一位,就从被除数中去一位进行补位,重复上面的计算
                    if dividend_pos < len(dividend_str):
                        last_str += dividend_str[dividend_pos]
                # 已经计算完了,每一步的商都在列表里,拼接起来,转成整数
                result = int(''.join(quotients))
                # 然后根据除数和被除数的负号,计算商的符号
                if flag1 == -1 and flag2 == -1 or flag1 == 1 and flag2 == 1:
                    pass
                else:
                    result = -result
        # 根据题目要求,如果数据不再 [−2^31,  2^31 − 1]范围内,就返回2^31-1
        # 如果严格要求来看,这里其实应该使用字符串进行比较,在result那一步也只保存成字符串,但我嫌麻烦,就这样偷懒了。
        # 毕竟想考较的应该主要是除法模拟吧?
        if (result < -(1 << 31)) or (result >= (1 << 31)):
            return (1 << 31) - 1
        else:
            return result


标题:leetcode题解第29题 Divide Two Integers (两数相除)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573024985893.html