T69. Sqrt(x)【Easy】
题目
写方法 int sqrt(int x)
计算并返回 x 的平方根
思路
哇这是数学啊！为难死我了！忘记了数学！
① 找到一个平方> x 的 r ,然后 把 r 减小凑出正确的解
② 若是简单的 -1 然后得到正确的值会超时
③ 所以要找到一个快速而又不会减的太快的方法
怎么找呢？咳，数学公式来说话（我竟然还记得一点数学）：
所以用下面的公式就很棒！
r = (r + x/r) / 2;
代码
代码取自 Top Solution，稍作注释
public int mySqrt(int x) {
// 要用long,因为后面要r*r会超过int
long r = x;
// 数学推导，慢慢减少
while (r*r > x)
r = (r + x/r) / 2;
return (int) r;
}
