原题
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例1:
输入: 4
输出: 2
示例2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
解法
思想
二分法
代码
class Solution {
public int mySqrt(int x) {
//为了防止end * end 超过int范围,这里统一使用使用long
long longx = x;
long start = 0;
long end = x/2;
long mid;
while(start<=end){
mid = (end+start)/2;
if(mid*mid == longx) return (int)mid;
if(mid*mid < longx) {
start = mid + 1;
if(start*start>longx) return (int)mid;
}
else if(mid*mid > longx) {
end = mid - 1;
if(end*end<longx) return (int)end;
}
}
return (int)start;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode69-x%e7%9a%84%e5%b9%b3%e6%96%b9%e6%a0%b9/