关关的刷题日记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;
    }
};

照顾好自己的身体，控制好自己的情绪，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。