LeetCode探索の旅(100)-29 Divide Two Integer
2187 ワード
今日はLeetCode、29番、2つの整数を塗り続けます.
分析:テーマの要求は乗算、除法、および余を求め、型を求めることができない以上、2つの数を使って減算することができます.絶えず減算することによって、結果と被減数の間の大きさを判断し、結果が被減数より小さくなるまで、減算回数を統計することは、2つの整数を除いた結果である.
質問:1、整数があふれている場合;2、正負号の判断;3、サイクル相減算の場合、計算時間を短縮する問題であれば、二乗を採用して計算時間を短縮することができる.
C++コードを添付します.
コンパクトなコードを添付します.
Pythonコードを添付します.
分析:テーマの要求は乗算、除法、および余を求め、型を求めることができない以上、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