关关的刷题日记78 – Leetcode 69. Sqrt(x)- 专知

会员服务 ·

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记78 – Leetcode 69. Sqrt(x)

题目

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4 Output: 2 Example 2:

Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

题目让我们求x的平方根，如果有小数部分，只取整数部分。

方法1：二分查找求平方根，题目设置long的目的是为了防止越界。

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

师父不让用long来做这个题目。然后又仔细想了一下：
方法2：先想到如果存在溢出，肯定是右边界过大，所以先求了一下(int)sqrt(INT_MAX)=46340, 设置右边界的初始值为46340。

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

方法3：不过我们一般不采用方法2来做，一般用下面的方法来做，巧妙地避免了每个可能溢出的点。

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