LeetCode

LeetCode-29 两数相除

nkul · 9月30日 · 2020年 · 34次已读

1、不能使用乘除,只能使用加减

2、提示第三点告诉计算过程中要使用long long 类型

3、int相除本身就可以溢出,如:\(k = \frac{ \left( – \left( 2 \right) ^{ \mathrm{31} } \right) }{ \left( – 1 \right) }\),该数溢出;

通常而言(只考虑两者都为正数),只用加减法做\(y/x\) 的方法为:\(y -= x\),做的次数就是商。但是若y = INT_MAX ,x = 1 ,显然时间太长,不会AC。因为考虑优化!

令\(Y/X= K\),将K用二进制表示为\(\sum2^k\),则k的取值只有0-31共32个数。

又有,\(Y = KX = \sum 2^k * X\),因此从\(2^{31} * X\)开始到\(2^0 * X\),用Y 和\( 2^k * X\)比较,就可以确定K的二进制表示的1所在位置以及0所在的位置!

class Solution {
public:
    int divide(int dividend, int divisor) {
        //为了书写方便
        typedef long long LL;
        vector exp;

        //判断符号
        bool is_minus = false;
        if( (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) 
            is_minus = true ;

        //取绝对值,但是一定要强制类型转换,因为INT_MIN取绝对值会溢出
        LL a = abs((LL)dividend) , b = abs((LL)divisor);

        LL res = 0;

        //将b 2b 4b …… 2^31b存起来
        for(LL i = b ; i <= a ; i = i + i) exp.push_back(i);

        //从最大值开始比较,判断该位置是否为1
        for(int i = exp.size() - 1;i >=0 ; i --){
            if( a >= exp[i]){
                a -= exp[i];
                //res左移可能会溢出,故用ll类型
                res += 1ll << i;
            }
        }
        if(is_minus) res = -res ;
        if(res > INT_MAX || res < INT_MIN) return INT_MAX;
        return res;

    }
};

1、取绝对值,但是一定要强制类型转换,因为INT_MIN取绝对值会溢出

2、res左移可能会溢出,故用ll类型



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!