LeetCode29 两数相除

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

LeetCode第29题

问题描述

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

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

示例 1:

1
2
输入: dividend = 10, divisor = 3
输出: 3

示例 2:

1
2
输入: dividend = 7, divisor = -3
输出: -2

说明:

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

解题思路

除法是乘法的逆运算，假设 dividend / divisor = n，那么有dividend = divisor * n，亦可表示为n个数进行累加dividend = divisor + … + divisor。解答本题的基本思路即通过对除数进行累加直到超过被除数，累加的次数即为商。显然，这种方法运行效率不高，评测执行超时。那有没有什么方法在此算法基础上提升效率了，先来看个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
求 12/2 的商，转换成加法，即：
12 = 2 + 2 + 2 + 2 + 2 + 2
共累加6次，即商为6。

通过观察发现，每次都是累加同一个数字，能不能减少加法运算，快速逼近12？答案对除数进行移位操作。

轮次  |     移位        |    商
1        4 (2 <<= 1)       2 (1 <<= 1)
2        8 (4 <<= 1)       4 (2 <<= 1)
3        16 (8 <<= 1) 退出循环

经过两轮循环，除数为8，商为4，余数为12 - 8 = 4。然后继续使用相同的方法计算4/2的商。

轮次  |     移位    |    商
1       4 (2 <<= 1)     2 (1 <<= 1)
2       8 (4 <<= 1)  退出循环

则12/2商为 4 + 2 = 6。通过此算法，共减少了3次加法运算。

通过对除数进行移位操作可较少加法次数，从而提升算法执行效率。考虑到被除数或除数可能出现负数情况，可先计算商的正负情况，然后取被除数和除数的绝对值进行除法运算，最后再设置商的符号。

算法伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
令商result = 1 
计算商是否为负数 neg = (dividend < 0) ^ (divisor < 0)
取被除数、除数绝对值 dividend = abs(dividend), divisor = abs(divisor)
假如 dividend < divisor, 则返回0
初始化count, n = 1, divisor
while (n << 1) <= dividend
   n <<= 1
   count <<= 1
result += count
令dividend = dividend - n, 重复步骤4
如果reg是负数, 则返回-result, 否则返回result (需考虑整数溢出情况)

代码

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
26
27
28
29
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        neg  = (dividend < 0) ^ (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        
        if dividend < divisor:
            return 0
        
        if divisor == 1:  # 当除数是1时，商直接设置为dividend
            result = dividend
        else:
            result = 1
            tmp = divisor
            while (tmp << 1) <= dividend:
                tmp <<= 1
                result <<= 1

            result += self.divide(dividend - tmp, divisor)
        
        # 处理正整数除法溢出的情况
        if result >= 2 ** 31 and not neg:
            return 2 ** 31 - 1
        
        return -result if neg else result

以上代码使用Python3编写，注意Python3没有long类型，int整形没有大小限制。

相关文章
感谢你对我的支持，让我继续努力分享有用的技术和知识点