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

  |  

摘要: 本文详细拆解 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