x的平方根

x的平方根

这个题虽然是简单题,但还是踩了蛮多坑的。这题一开始,一看我还以为是浮点数二分,最后答案是整数,其实用的是整数二分。

1.整数二分,浮点数二分的判定,看答案是否位整数,或浮点数。

2.这题有两处要防止越界,第二个坑点。

第一个是求mid的时候(l+r+1)可能越界,mid*mid可能越界

3.这题要求向下取整求其小于等于答案的最大值,第三个坑点。

我们结合答案来看看怎么操作。

1.这里我们可以用1ll,来防止l+r+1的越界,把1ll插入到l+r的中间,1ll会先计算l+1ll或者r+1ll把他们呢转换成longlong类型的变量。

2.mid*mid这里的越界,我们可以把mid除以过去。

3.由于这个数的算数平方根结果大多数为浮点数,而我们要向下取整,所以我们要取小于等于它的最大数。if里面的符号为《=;

class Solution {
public:
    int mySqrt(int x) {
    int l=0,r=x;
    while(l<r){
        int mid=l+1ll+r>>1;
        if(mid<=x/mid)l=mid;
        else r=mid-1;
    }
    return l;
    }
};

上一篇:[ARC124E]Pass to Next


下一篇:图的前向星表示