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.
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.
本题要对一个数开平方根。相当于LeetCode Valid Perfect Square的逆过程，很多方法都可以通用。 解法1。直接借用LeetCode Valid Perfect Square提到的牛顿法开方，代码如下：
class Solution {
public:
int mySqrt(int x)
{
long long y = x;
while (y * y > x) {
y = (y + x / y) / 2;
}
return y;
}
};
本代码提交AC，用时6MS。
解法2。二分搜索，由于sqrt(x)不可能超过x/2+1（查看两个函数图像），所以可以在[0,x/2+1]范围内二分搜索，因为是向下取整，所以返回的是r，代码如下：
class Solution {
public:
int mySqrt(int x)
{
long long l = 0, r = x / 2 + 1;
while (l <= r) {
long long mid = (l + r) / 2;
long long prod = mid * mid;
if (prod == x)
return mid;
if (prod < x)
l = mid + 1;
else
r = mid – 1;
}
return r;
}
};
本代码提交AC，用时6MS。
三刷。暴力枚举：
class Solution {
public:
int mySqrt(int x) {
long long xx = x;
if (x == 1)return 1;
long long i = 1;
for (; i < xx; ++i) {
if (i*i > xx)break;
}
return i - 1;
}
};本代码提交AC，用时16MS，还是用前两个方法吧。
对于函数$$f(x)=x^2-num$$，$$f'(x)=2x$$，所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$
所以我们可以初始代入$$x_n=num$$，然后不断用牛顿法，直到x*x<=num时，如果x*x==num，则num为完全平方数，否则不是。
关于牛顿法用于开放的原理介绍，
For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example: