【LeetCode】29. 两数相除

class Solution {
public:
    int divide(int a,int b) {
    if (a == INT_MIN && b == -1)
        return INT_MAX;

    if(a!=INT_MIN && b== INT_MIN)  //除数是INT_MIN特殊判定
        return 0;

    if(a==b)
        return 1;

    int sign = 0;

    if ((a > 0 && b < 0) || (a < 0 && b > 0))
        sign = 1;

    if (b == 1)
        return a;

    if(b==-1)
        return -a;

    if(a==-b)
        return -1;

    if (a > 0)
        a = -a;
    if (b > 0)
        b = -b;

    int base = 1, cp = b,ans=0;

    while (a <= b)
    {
        cp=b; //存一下当前循环的除数
        base = 1;
        while(cp>=0xc0000000&&a<=cp+cp) 
        {
            base+=base;
            cp+=cp;
        }
        ans+=base;
        a-=cp;
    }

    if(sign)
        ans=-ans;

    return ans;
    }
};

主要思想首先对可能超时或者溢出的结果进行特殊判定。

对需要进行计算的值,找到最接近被除数a的2^k值,a>cp+cp时则找到了这个值,否则cp和商扩倍;

当找到了这个商后,则加到结果中,被除数减去这个商,继续重复这个循环,直到被除数大于除数,返回结果。

 

这是一种优化算法,效率接近logn,前面带一常数但不是n

上一篇:Docker容器和宿主机互传文件


下一篇:linux系统命令