1. 题目
Implement int sqrt(int x).
Compute and return the square root of x.
注：对于5，6，7，8等都返回2.
2. 思路
用牛顿开方法计算。
原理：3. 代码
class Solution {public: // 牛顿迭代法 X[n+1] = 1/2 * (X[n] + a/X[n]), a is x^2 // 单纯的整数开方数直接二分迭代 int mySqrt(int x) { if (x == 0) return 0; int y = x/2; while (true) { y = max(y, 1); long long k1 = 1L * y * y; long long k2 = 1L * (y+1)*(y+1); if (k1 <= x && k2 > x) { return y; } y = (y + x / y) / 2; } return y; }};