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

关关的刷题日记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)。 同时请,关注我们的公众号,获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。

图片

展开全文
相关主题
Top
微信扫码咨询专知VIP会员