算法leetcode

【分类讨论】力扣29-两数相除

字数统计: 1.6k字   |   阅读时长: 6分
,

摘要: 本文详细拆解 leetcode 29-两数相除，主要涉及分类讨论。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 面试好题连载 中，我提到了我认为的适合作为面试题的标准，这里复习一下：

对于适合面试的题目，以下几个要点中 (1)(2)(5)必须满足，(3)(4)至少满足一个：

(1) 考查基础的数据结构和主流算法，避开邪门算法和脑筋急转弯
(2) 暴力方法很容易想到
(3) 最好有两种以上的优化方式
(4) 最好有两三道递进的题可以放到一起
(5) 最终代码不长

今天我们看一个分类讨论的题，leetcode第29题，【29. 两数相除】。

要解决本题，需要先将问题拆解成两部分，第一步是如果两个数都是非负数，如何不用乘法、除法和mod运算符实现除法。这是单独的一道题，属于数字运算这个场景，这个场景可以举出一些其它类似的题目，例如下面这 4 道。算法上要用快速乘法，这是快速幂的变种，除此外还有模下快速幂等变种。

第二部分是对除数和被除数的分类讨论。这不是算法，而是一种思想，这一块也可以举出一些以分类讨论思想为核心的题目，例如

基于以上分析 (4) 满足。本题的考察点是数字运算，快速幂和分类讨论，均为基础算法，因此 (1) 满足。

下面我们来看一下这个题

题目描述

给定两个整数，被除数 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

提示

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

算法：分类讨论

首先我们假设有一个函数 _divide(dividend, divisor)，实现了当 dividend 和 divisor 均大于 0 时，不用 *, /, % 返回 dividend 除以 divisor 的结果。

在有了函数 _divide() 的条件下，我们对 dividend 和 divisor 的正负进行分类讨论。dividend 和 divisor 哪个小于零，就取相反数放进 _divide() 里计算即可。

但是还有一些边界问题需要单独讨论，主要有两点

  • 第一个是 0 的讨论，这个比较简单，divisor 题目里保证了不为 0，如果 dividend 为零，则直接返回 0 即可
  • 另一个是 INT_MIN 的讨论，由于 INT_MIN = - 2 ^ 31, INT_MAX = 2 ^ 31 - 1 中间差着 1，因此 divisor 和 dividend 任意一个为 INT_MIN，取相反数后就溢出了，需要特殊处理。

分类讨论的整体算法如下

对 dividend 和 divisor 的分类讨论

下面我们看 _divide(dividend, divisor) 如何实现，算法与快速幂很像。

首先如果 dividend < divisor，那么直接返回 0。然后我们维护一个变量 div，初始化为 divisor；同时维护一个因子 iter，表示当前的 div 是多少个 divisor，初始化为 1。维护一个最终答案变量 ans，初始化为 0。然后我们开始迭代 dividend，直至 dividend < div。

每一轮迭代，把 ans 加上 iter，dividend 减去 div，然后 div 乘以 2，iter 也乘以 2，如果仍然 dividend >= div 继续下一轮迭代。

但要注意 div 乘以 2 之前要判断是否会溢出，也就是判断 INT_MAX - div >= div 即可。

迭代完成后 dividend < div，但是 dividend 可能还会大于 divisor，因此还要继续迭代，只是每轮迭代后，将 div 和 iter 分别除以 2。直至 div 等于 0。

代码(C++)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int divide(int dividend, int divisor) {
        // dividor 不为零
        if(dividend == 0) return 0;
        if(divisor == INT_MIN)
        {
            if(dividend == INT_MIN)
                return 1;
            else
                return 0;
        }
        if(dividend == INT_MIN)
        {
            if(divisor > 0)
                return -1 - _divide(-(dividend + divisor), divisor);
            else if(divisor == -1)
                return INT_MAX;
            else
                return 1 + _divide(-(dividend - divisor), -divisor);
        }
        // [-(2^31 - 1) .. 0 .. 2^31 - 1]
        if(dividend > 0 && divisor < 0) return -_divide(dividend, -divisor);
        else if(dividend < 0 && divisor > 0) return -_divide(-dividend, divisor);
        else if (dividend < 0 && divisor < 0) return _divide(-dividend, -divisor);
        else return _divide(dividend, divisor);
    }

private:
    int _divide(int dividend, int divisor) {
        if(dividend < divisor) return 0;

        int res = 0;

        int div = divisor;
        int iter = 1;
        dividend -= div;
        res += iter;
        while(dividend >= div && INT_MAX - div >= div && dividend > (div * 2))
        {
            div = div * 2;
            iter = iter * 2;
            dividend -= div;
            res += iter;
        }
        while(div > 0)
        {
            while(dividend - div >= 0)
            {
                res += iter;
                dividend -= div;
            }
            div = div /= 2;
            iter = iter /= 2;
        }
        return res;
    }
};

代码(Python)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 数值范围 [−2^31,  2^31 − 1] 结果溢出则返回 2^31-1
        self.INT_MIN = -(2 ** 31)
        self.INT_MAX = 2 ** 31 - 1
        if dividend == 0:
            return 0
        if divisor == self.INT_MIN:
            if dividend == self.INT_MIN:
                return 1
            else:
                return 0
        if dividend == self.INT_MIN:
            if divisor > 0:
                return -1 - self._divide(-(dividend + divisor), divisor)
            elif divisor == -1: # 结果溢出
                return self.INT_MAX
            else:
                return 1 + self._divide(-(dividend - divisor), -divisor)
        # [-(2^31 - 1) .. 0 .. 2^31 - 1]
        if dividend < 0 and divisor < 0:
            return self._divide(-dividend, -divisor)
        elif dividend > 0 and divisor < 0:
            return -self._divide(dividend, -divisor)
        elif dividend < 0 and divisor > 0:
            return -self._divide(-dividend, divisor)
        else:
            return self._divide(dividend, divisor)

    def _divide(self, dividend: int, divisor: int) -> int:
        if dividend < divisor:
            return 0

        res = 0
        div = divisor
        i = 1
        dividend -= div
        res += i
        while dividend >= div and self.INT_MAX - div >= div and dividend > (div * 2):
            div = div * 2
            i = i * 2
            dividend -= div
            res += i
        while div > 0:
            while dividend - div >= 0:
                res += i
                dividend -= div
            div = div //= 2
            i = i //= 2
        return res
Share