Leetcode第29题(两数相除)

题目描述:

给定两个整数，被除数 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> 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;
    }
};