leetcode题解第29题 Divide Two Integers （两数相除）

墨蓝 2023-05-29 13:17 4阅读 0赞

题目的大意如下：

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

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

且在此之外，还有几点额外说明：

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

样例输入1：

dividend = 10, divisor = 3

样例输出1：

样例输入2：

dividend = 7, divisor = -3

样例输出2：

-2

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

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

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

有什么优化的方法吗？

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

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

假设我们把摆竖式的过程称为复杂除法，第一种方法称为简单除法。那么当最坏的情况下，被除数为 2 31 − 1 2^\{31\}-1 231−1，除数为1， 2 31 − 1 = 2147483647 2^\{31\}-1 = 2147483647 231−1=2147483647，长度为10，我们需要做10次复杂除法。而每次复杂除法，我们都需要做一次简单除法。由于在摆竖式的过程中，取出的被除数的一部分的长度和除数的长度一般是相同的（当不相同时：被除数长度小，则直接商零，不需要计算；被除数长度大，需要的更多计算次数可以由前者平衡。所以这两种情况不会影响总的计算次数），那么一次简单除法的累加次数就不会超过10次。进而总的运算次数不超过  10 ∗ 10 = 100 10\*10=100 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

转载请注明出处：[https://blog.csdn.net/aaronjny/article/details/102935982][https_blog.csdn.net_aaronjny_article_details_102935982]

[https_blog.csdn.net_aaronjny_article_details_102935982]: https://blog.csdn.net/aaronjny/article/details/102935982