LeetCode 143. 两数相除
原题链接
中等
作者:
あ
,
2022-01-30 08:31:08
,
所有人可见
,
阅读 239
二分+思维+细节
思路
见: https://leetcode-cn.com/problems/divide-two-integers/solution/liang-shu-xiang-chu-by-leetcode-solution-5hic/
代码
class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend==INT_MIN)//越界判断
if(divisor==-1)
return INT_MAX;
else if(divisor==1)
return INT_MIN;
bool flag=false;
if(dividend>0)
{
flag=!flag;
dividend=-dividend;
}
if(divisor>0)
{
flag=!flag;
divisor=-divisor;
}
int left=0,right=INT_MAX;
while(left<right)
{
int mid=left+1+((right-left-1)>>1);
if(quick(dividend,divisor,mid)){
left=mid;
}
else
right=mid-1;
}
if(flag)
return -left;
return left;
}
bool quick(int x,int y,int z)
{
int result=0,add=y;
while(z)
{
if(z&1)
{
if(result<x-add)
return false;
result+=add;
}
if(z!=1)//正常来说z=1以后就结束了,add翻不翻倍无所谓,但是由于这里面有个影响结果的条件判断,所以必须加上这个z!=1的条件判断
{
if(add<x-add)
return false;
add+=add;
}
z>>=1;
}
return true;
}
};