Implementint sqrt(int x)
.
Compute and return the square root ofx.
x is guaranteed to be a non-negative integer.
这道题可以用二分法做, 即每次取[1, x/2]中值 (x/2因为只要sqrt大于2就一定会比x/2小), 判断mid ^ 2是大于还是小于等于x。 注意最开始的几个值可能溢出, 因此初始end 取46340即可。
还有可以用牛顿迭代法做. 每次取切线与0的交点r, 看r ^ 2 是否>x, 是则继续, 否则返回.
/*
* @lc app=leetcode id=69 lang=cpp
*
* [69] Sqrt(x)
*/
class Solution {
public:
int mySqrt(int x) {
int start = 1, end = min(x / 2, 46340);
while (start < end) {
int mid = start + (end - start) / 2;
if (mid * mid < x) start = mid + 1;
else end = mid;
}
return start * start > x ? start - 1 : start;
}
};
class Solution {
public int mySqrt(int x) {
long r = x;
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int) r;
}
}
未知.