实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
#include "_000库函数.h" //最简单想法，耗时长
class Solution {
public:
int mySqrt(int x) {
if (x <= )return x;
double n = ;//防止int溢出
while (++n) {
if (n*n > x) {
--n;
return (int)n;
}
else if (n*n == x)
return (int)n;
}
return ;//力扣非得要在这里加一个return,无语了
}
}; //用对折法
//因为x为int，最大为65536的平方
//贼鸡儿快，内存很少
class Solution {
public:
int mySqrt(int x) {
if (x <= )return x;
double min = , max = , mid = (int)((min + max)/);//防止int溢出
while (min < max&&mid*mid != x) {
if (mid*mid < x)min = mid + ;
else max = mid - ;
mid = (int)((min + max)/);
}
if (mid*mid > x)--mid;
return (int)mid;
}
}; //同样折半，更简洁
class Solution {
public:
int mySqrt(int x) {
if (x <= ) return x;
int left = , right = x;
while (left < right) {
int mid = left + (right - left) / ;
if (x / mid >= mid) left = mid + ;
else right = mid;
}
return right - ;
}
}; //更牛逼的方法
//用牛顿迭代法，记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，
//因为要求x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，可以求出递推式如下：
//
//xi + 1 = xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n / xi) / 2 class Solution {
public:
int mySqrt(int x) {
long res = x;
while (res * res > x) {
res = (res + x / res) / ;
}
return res;
}
};
void T069() {
Solution s;
cout << "2: " << s.mySqrt() << endl;
cout << "8: " << s.mySqrt() << endl;
cout << "0: " << s.mySqrt() << endl;
cout << "9: " << s.mySqrt()<<endl;
}