LeetCode 0029 - Divide Two Integers
# Hints
- 倍增
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given two integers and , divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing by .
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Note:
Both and will be 32-bit signed integers.
The will never be .
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: . For the purpose of this problem, assume that your function returns when the division result overflows.
# 题意
给定两个整数 和 ,求 的值,并且代码中不允许使用乘法和除法运算。如果答案超出int类型的表示范围则返回 。
# 题解
在不允许使用乘法和除法运算的情况下,容易想到用多次加减法来实现除法,当然对于 的数量级而言暴力加减法肯定是不行的。
为便于描述,令 分别表示 ,那么我们需要求 的值。
考虑倍增,以 的情况为例,我们知道 ,其中 均为非负整数。我们把 用二进制形式来表示,可以发现 。
这意味着我们只需遍历 ,不断地将 从 中减去并计数,即可在 即 的时间内完成 的计算,而 。
大体思路已经确定,但是细节上注意题目要求结果在int类型的表示范围内,这会导致很多问题。
我们固然可以将所有变量设为long long,但如果下次参数的范围就是long long呢?我们需要尝试仅用int解决问题,为此我们需要特殊处理 的情况,因而多了许多特判,详见代码实现,如果你不清楚这些特判存在的意义,可以尝试去掉特判后提交代码到LeetCode上。
细节问题:
注意特判非法运算的情况,不过本题保证了 不需要,否则一定不要忘了。
注意 没有超出int类型的表示范围而 超出了,因此取绝对值的时候需要使用一些手段避免越界。
注意特判 的情况。
注意直接遍历 的话 会发生越界,必须先计算出 的上界,即 。
# AC代码(使用long long)
class Solution {
typedef long long ll;
public:
int divide(int dividend, int divisor) {
// 特判:非法运算
if (dividend == 0) {
return 0;
}
if (divisor == 0) {
return MAX;
}
// 求解
ll a = abs((ll)dividend), b = abs((ll)divisor);
ll res = solve(a, b);
// 处理符号
if ((dividend > 0) != (divisor > 0)) {
res = -res;
}
// 处理越界
if (res < MIN || res > MAX) {
res = MAX;
}
// 返回
return (int)res;
}
// 解决
ll solve(ll a, ll b) {
// 主循环
ll res = 0;
for (int i = 31; i >= 0; i --) {
if (a >= (b << i)) {
a -= (b << i);
res += (1ll << i);
}
}
// 返回
return res;
}
// 常量
const int MAX = (1 << 31) - 1;
const int MIN = (1 << 31);
};
# AC代码(通用)
class Solution {
public:
int divide(int dividend, int divisor) {
// 特判:非法运算
if (dividend == 0) {
return 0;
}
if (divisor == 0) {
return MAX;
}
// 特判:防止 MIN / 1
if (divisor == 1) {
return dividend;
}
// 特判:防止 x / MIN
if (divisor == dividend) {
return 1;
}
if (divisor == MIN) {
return 0;
}
// 特判:防止 MIN / -1
if (dividend == MIN && divisor == -1) {
return MAX;
}
// 求解
int res;
if (dividend == MIN) {
res = solve(abs(dividend + abs(divisor)), abs(divisor)) + 1;
} else {
res = solve(abs(dividend), abs(divisor));
}
// 处理符号
if ((dividend > 0) != (divisor > 0)) {
res = -res;
}
// 返回
return res;
}
// 解决
int solve(int a, int b) {
// 预处理
int logk = 0;
while ((b << logk) <= (MAX >> 1)) {
logk ++;
}
// 主循环
int res = 0;
for (int i = logk; i >= 0; i --) {
if (a >= (b << i)) {
a -= (b << i);
res += (1 << i);
}
}
// 返回
return res;
}
// 常量
const int MAX = (1 << 31) - 1;
const int MIN = (1 << 31);
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01