Powered By GitBook
69.Sqrt
难度:Easy

69.Sqrt(x)

Implement int sqrt(int x).
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.
1
Example 1:
2
3
Input: 4
4
Output: 2
5
Example 2:
6
7
Input: 8
8
Output: 2
9
Explanation: The square root of 8 is 2.82842..., and since
10
the decimal part is truncated, 2 is returned.
Copied!
求平方根,可以尝试采用二分法;
1
class Solution {
2
int mySqrt(int start,int end, int x)
3
{
4
long int mid=(start+end)/2;
5
if(mid*mid <=x && (mid+1)*(mid+1)>x) return mid;
6
else if(mid*mid>x ) return mySqrt(start, mid,x);
7
else return mySqrt(mid,end,x);
8
}
9
public:
10
int mySqrt(int x) {
11
if(x==0 || x==1) return x;
12
return mySqrt(0,x,x) ;
13
}
14
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了90.73%的用户 内存消耗 :8.2 MB, 在所有 C++ 提交中击败了81.90%的用户
Last modified 2yr ago
Copy link
Contents
69.Sqrt(x)