LeetCode探索の旅(100)-29 Divide Two Integer


今日はLeetCode、29番、2つの整数を塗り続けます.
分析:テーマの要求は乗算、除法、および余を求め、型を求めることができない以上、2つの数を使って減算することができます.絶えず減算することによって、結果と被減数の間の大きさを判断し、結果が被減数より小さくなるまで、減算回数を統計することは、2つの整数を除いた結果である.
質問:1、整数があふれている場合;2、正負号の判断;3、サイクル相減算の場合、計算時間を短縮する問題であれば、二乗を採用して計算時間を短縮することができる.
C++コードを添付します.
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==INT_MIN&&divisor==-1)
            return INT_MAX;
        if(dividend==INT_MIN&&divisor==1)
            return INT_MIN;
        int flag=1;
        if((long long)dividend*(long long)divisor<0)
            flag=-1;
        int re=0;
        long long m=abs((long long)dividend);
        long long n=abs((long long)divisor);
        while(m>=n)
        {
            long long p=1,t=n;
            while(m>(t<<1))
            {
                t<<=1;
                p<<=1;
            }
            re+=p;
            m-=t;
        }
        return re*flag;
    }
};

コンパクトなコードを添付します.
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) {
            return INT_MAX;
        }
        long dvd = labs(dividend), dvs = labs(divisor), ans = 0;
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
        while (dvd >= dvs) {
            long temp = dvs, m = 1;
            while (temp << 1 <= dvd) {
                temp <<= 1;
                m <<= 1;
            }
            dvd -= temp;
            ans += m;
        }
        return sign * ans;
    }
};

Pythonコードを添付します.
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend==-2**31 and divisor==-1:
            return -dividend-1
        flag = -1 if (dividend <0 and divisor >0) or (dividend>0 and divisor<0) else 1
        m=abs(dividend)
        n=abs(divisor)
        re=0
        while m>=n:
            p=1
            t=n
            while m>=(t<<1):
                t<<=1
                p<<=1
            m-=t
            re+=p
        return re*flag