標簽： C++ 算法 LeetCode
每日算法——leetcode系列
問題 Divide Two Integers
Difficulty: Medium
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
class Solution {
public:
int divide(int dividend, int divisor) {
}
};
翻譯
兩數(shù)相除
難度系數(shù)：中等
不用乘浴骂、除、模操作實現(xiàn)兩數(shù)相除
如果溢出，返回MAX_INT蜓席。
思路
假設： n = dividend/divisor divided和divisor都為正整數(shù)
則： dividend = n * divisor = divisor + ... + divisor(n個divisor) + 余數(shù)
dividend >= n * divisor = divisor + ... + divisor(n個divisor)
divided - (divisor + ... + divisor(n個divisor)) >= 0
這樣可以每次減去被除數(shù)徙赢，得到n divisor為0時自娩，個人覺得應該算溢出
由于可以用位運算，可以進一步優(yōu)化
每次divisor << 1, 循環(huán)執(zhí)行相當于：
1個divisor + 2個divisor + 4個divisor + 8個divisor ... <= divided
把1悼潭， 2钥顽， 4 义屏， 8等加起來就好, 這樣會存在余數(shù)>divisor的情況
這種情況就把余數(shù)作為divided，再循環(huán)執(zhí)行就好
代碼
class Solution {
public:
int divide(int dividend, int divisor) {
int sign = 1;
// 異號
if ((dividend >0 && divisor < 0) || (dividend < 0 && divisor >0)){
sign = -1;
}
// 當為INT_MIN時耳鸯，轉成正整數(shù)時會有溢出湿蛔， 所以用unsigned int來存
unsigned int divd = dividend > 0 ? dividend : -dividend;
unsigned int divr = divisor > 0 ? divisor : -divisor;
unsigned reslut = 0;
while (divd >= divr) {
int n = 1;
unsigned tempDivr = divr;
while (divd >= tempDivr) {
divd -= tempDivr;
reslut += n;
if (tempDivr < (INT32_MAX >> 1)){
// 如果大于INT32_MAX >> 1 那么tempDivr * 2會溢出
tempDivr = tempDivr << 1; // 相當tempDivr += tempDivr
n = n << 1; // n += n
}
}
}
if (reslut > INT32_MAX && sign == 1){
return INT32_MAX;
}
return sign * reslut;
}
};
