你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

LeetCode——整数除法 C++

2021/12/1 16:37:15

 题目描述:取自LeetCode

 

         这道题的难点在于int边界值的判断以及采用减法代替除法时循环效率问题。循环效率问题可以采用逐步给除数加倍的方式(幂加速)来优化效率,防止超时情况发生。

 完整代码如下:

int divide(int a, int b) {
        long num=0,v=0;//用long来记录变量的值,防止溢出,v来记录最后是否需要加负号
        long a1=a,b1=b;
        if(a<0)v++;
        if(b<0)v++;
        
        a1=abs(a1);
        b1=abs(b1);
        while(a1>=b1){
            a1-=b1;
            num++;
            long i=b1,j=1;//记录一下b的值以及倍数
            while(a1>i+i){//采用每次给b加倍的方式来加速循环,否则会出现超时问题
                j+=j;//倍数增加
                a1-=i+i;
                i+=i;
                num+=j;
            }
            if(v==1&&num==pow(2,31)){//溢出的处理
                 return -num;
            }
            else if(v!=1&&num==pow(2,31)-1)return num;

        }
        
        if(v==1)return -num;
        return num;

    }