关关的刷题日记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）。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2017-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录