力扣算法题—069x的平方根

实现 int sqrt(int 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;
}
上一篇:判断ios还是android


下一篇:EXT 组件一些属性与方法(Tree)