第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0029. 两数相除

题目地址(29. 两数相除)

题目描述

1
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
2
3
返回被除数 dividend 除以除数 divisor 得到的商。
4
5
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
6
7
8
9
示例 1:
10
11
输入: dividend = 10, divisor = 3
12
输出: 3
13
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
14
示例 2:
15
16
输入: dividend = 7, divisor = -3
17
输出: -2
18
解释: 7/-3 = truncate(-2.33333..) = -2
19
20
21
提示:
22
23
被除数和除数均为 32 位有符号整数。
24
除数不为 0。
25
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。
Copied!

前置知识

  • 二分法

公司

  • Facebook
  • Microsoft
  • Oracle

思路

符合直觉的做法是,减数一次一次减去被减数,不断更新差,直到差小于 0,我们减了多少次,结果就是多少。
核心代码:
1
let acc = divisor;
2
let count = 0;
3
4
while (dividend - acc >= 0) {
5
acc += divisor;
6
count++;
7
}
8
9
return count;
Copied!
这种做法简单直观,但是性能却比较差. 下面来介绍一种性能更好的方法。
29.divide-two-integers
通过上面这样的分析,我们直到可以使用二分法来解决,性能有很大的提升。

关键点解析

  • 正负数的判断中,这样判断更简单。
1
const isNegative = dividend > 0 !== divisor > 0;
Copied!
或者利用异或:
1
const isNegative = dividend ^ (divisor < 0);
Copied!

代码

  • 语言支持:JS, Python3, CPP
1
/*
2
* @lc app=leetcode id=29 lang=javascript
3
*
4
* [29] Divide Two Integers
5
*/
6
/**
7
* @param {number} dividend
8
* @param {number} divisor
9
* @return {number}
10
*/
11
var divide = function (dividend, divisor) {
12
if (divisor === 1) return dividend;
13
14
// 这种方法很巧妙,即符号相同则为正,不同则为负
15
const isNegative = dividend > 0 !== divisor > 0;
16
17
const MAX_INTERGER = Math.pow(2, 31);
18
19
const res = helper(Math.abs(dividend), Math.abs(divisor));
20
21
// overflow
22
if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) {
23
return MAX_INTERGER - 1;
24
}
25
26
return isNegative ? -1 * res : res;
27
};
28
29
function helper(dividend, divisor) {
30
// 二分法
31
if (dividend <= 0) return 0;
32
if (dividend < divisor) return 0;
33
if (divisor === 1) return dividend;
34
35
let acc = 2 * divisor;
36
let count = 1;
37
38
while (dividend - acc > 0) {
39
acc += acc;
40
count += count;
41
}
42
// 直接使用位移运算,比如acc >> 1会有问题
43
const last = dividend - Math.floor(acc / 2);
44
45
return count + helper(last, divisor);
46
}
Copied!
Python3 Code:
1
class Solution:
2
def divide(self, dividend: int, divisor: int) -> int:
3
"""
4
二分法
5
:param int divisor
6
:param int dividend
7
:return int
8
"""
9
# 错误处理
10
if divisor == 0:
11
raise ZeroDivisionError
12
if abs(divisor) == 1:
13
result = dividend if 1 == divisor else -dividend
14
return min(2**31-1, max(-2**31, result))
15
16
# 确定结果的符号
17
sign = ((dividend >= 0) == (divisor >= 0))
18
19
result = 0
20
# abs也可以直接写在while条件中,不过可能会多计算几次
21
_divisor = abs(divisor)
22
_dividend = abs(dividend)
23
24
while _divisor <= _dividend:
25
r, _dividend = self._multi_divide(_divisor, _dividend)
26
result += r
27
28
result = result if sign else -result
29
30
# 注意返回值不能超过32位有符号数的表示范围
31
return min(2**31-1, max(-2**31, result))
32
33
def _multi_divide(self, divisor, dividend):
34
"""
35
翻倍除法,如果可以被除,则下一步除数翻倍,直至除数大于被除数,
36
返回商加总的结果与被除数的剩余值;
37
这里就不做异常处理了;
38
:param int divisor
39
:param int dividend
40
:return tuple result, left_dividend
41
"""
42
result = 0
43
times_count = 1
44
while divisor <= dividend:
45
dividend -= divisor
46
result += times_count
47
times_count += times_count
48
divisor += divisor
49
return result, dividend
Copied!
CPP Code:
1
class Solution {
2
public:
3
int divide(int dividend, int divisor) {
4
if (!divisor) return 0; // divide-by-zero error
5
bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2);
6
if (pos1) dividend = -dividend;
7
if (pos2) divisor = -divisor;
8
int q = 0, d = divisor, t = 1;
9
while (t > 0 && dividend < 0) {
10
if (dividend - d <= 0) {
11
dividend -= d;
12
q -= t;
13
if ((INT_MIN >> 1) < d) {
14
t <<= 1;
15
d <<= 1;
16
}
17
} else {
18
d >>= 1;
19
t >>= 1;
20
}
21
}
22
return pos? -q : q;
23
}
24
};
Copied!
复杂度分析
  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(1)$

相关题目

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。