leetcode【69】Sqrt(x)
程序员文章站
2022-03-19 11:57:02
...
问题描述:
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4 Output: 2
Example 2:
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
源码:
最简单的方法
库函数,不合规矩。
class Solution {
public:
int mySqrt(int x) {
return int(sqrt(x));
}
};
暴力低效法:
class Solution {
public:
int mySqrt(int x) {
unsigned int i=0;
for(i=0; i<=x/2; i++){
if(i*i<=x && (i+1)*(i+1)>x)
break;
}
return i;
}
};
分治法:
大佬的方法,分治法,恍然大悟。
class Solution {
public:
int mySqrt(int x) {
if(x==0) return 0;
unsigned int left=1, right=x/2+1, mid=0;
while(left<=right){
mid = (left+right)/2;
if(mid<x/mid) left = mid+1;
else if(mid>x/mid) right = mid-1;
else{
return mid;
}
}
return right;
// return 0;
}
};
上一篇: LeetCode69题