题目描述:
给定两个整数,被除数 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, pair 中first存储的是n * y, second存储的是n ,(例如 x = 10 , y = 3, 那么vector> exp中存储的数字就为exp[0] = {-3, -1}, exp[1] = {-6,-2}, exp[2] = {-9,-3})。 最后计算结果的时候逆序遍历exp, 如果当前exp[i].first >= x (因为此时是负数), 那么ans+=exp[i].second, 然后x的值减去当前符合条件的exp[i].first的值。如果结果为负数直接返回ans即可, 如果是正数, ans == INT_MIN 说明将ans转成负数后会超出存储范围, 因此直接返回INT_MAX, 否则返回 -ans。x 为 被除数, y 为除数。
class Solution {
public:
int divide(int x, int y) {
int sign = (x > 0 && y < 0) || (x < 0 && y > 0); //记录结果正负
//将其转换为负数,因为负数的范围更大一点
if(x > 0) x = -x;
if(y > 0) y = -y;
//将2^k * y 与 2^k 存入一个pair中
vector<pair<int,int>> exp;
for(int i = y,j = -1; i >= x; i += i,j += j){
exp.push_back({i,j});
if(i < INT_MIN / 2) break;
}
//计算结果
int ans = 0;
for(int i = exp.size() - 1;i >= 0;i--){
if(exp[i].first >= x){
ans += exp[i].second;
x -= exp[i].first;
}
}
//返回结果
if(sign) return ans; //结果为负数
if(ans == INT_MIN) return INT_MAX; //为正数越界
return -ans;
}
};