赞
踩
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
二分法是我能想到的第一个方法,取两个指针。一个指向最大值一个指向最小值。然后每次循环除二,判断平方数是否大于还是小于输入。直到大的值减去小的值的差值为1。
class Solution { public: int mySqrt(int x) { if(x==0) return 0; if(x==1) return 1; //if(x>=9&&x<=15) // return 3; long int temp1=pow(2,16); long int temp2=1; int temp; while(temp1-temp2>1) { //cout<<"temp1: "<<temp1<<"temp2: "<<temp2<<endl; if(temp1*temp1==x) return temp1; if(temp2*temp2==x) return temp2; if((temp1*temp1)>x&&(temp2*temp2<x)) { //cout<<"(temp1*temp1)>x&&(temp2*temp2<x)"<<endl; temp1=(temp1+temp2)/2; } else if(temp1*temp1<x&&temp2*temp2<x) { //cout<<"temp1*temp1<x&&temp2*temp2<x"<<endl; temp2=temp1; temp1*=2; } else if(temp1*temp1>x&&temp2*temp2>x) { //cout<<"temp1*temp1>x&&temp2*temp2>x"<<endl; temp1=temp2; temp2/=2; } } if(temp1*temp1==x) return temp1; if(temp1*temp1<x) { temp1+=1; if(temp1*temp1>x) temp1-=1; return temp1; } return temp2; } };
这里有个小bug。因为是大的数字加小的数字除二之后两者的差值满足一跳出循环,当输入为9时。上值为4下值为1,在该区间内。所以得到新的上值(1+4)/2=2满足上式减下式为一。得到新的上值为2.但其实这时候输出应该为3.所以后面多加了个判断。
官方解答:
class Solution { public: int mySqrt(int x) { int l = 0, r = x, ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if ((long long)mid * mid <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } };
「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数,得到我们想要计算的结果。
由于计算机无法存储浮点数的精确值(浮点数的存储方法可以参考 IEEE 754,这里不再赘述),而指数函数和对数函数的参数和返回值均为浮点数,因此运算过程中会存在误差。例如当 x=2147395600 时, lnx的计算结果与正确值 4634046340 相差
1
0
−
11
10^{-11}
10−11
,这样在对结果取整数部分时,会得到 4633946339 这个错误的结果。
因此在得到结果的整数部分ans 后,我们应当找出 ans 与ans+1 中哪一个是真正的答案。
class Solution {
public:
int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = exp(0.5 * log(x));
return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}
};
牛顿迭代法是一种可以用来快速求解函数零点的方法。
为了叙述方便,我们用 C 表示待求出平方根的那个整数。显然,C 的平方根就是函数
的零点。
牛顿迭代法的本质是借助泰勒级数,从初始值开始快速向零点逼近。我们任取一个
x
0
x_0
x0 作为初始值,在每一步的迭代中,我们找到函数图像上的点
(
x
i
,
f
(
x
i
)
)
(x_i,f(x_i))
(xi,f(xi)) 过该点作一条斜率为该点导数
f
,
(
x
i
)
)
f^,(x_i))
f,(xi)) 的直线,与横轴的交点记为
x
i
+
1
x_{i+1}
xi+1。
x
i
+
1
x_{i+1}
xi+1相较于
x
i
x_i
xi而言距离零点更近。在经过多次迭代后,我们就可以得到一个距离零点非常接近的交点。下图给出了从
x
0
x_0
x0开始迭代两次,得到
x
1
x_1
x1和
x
2
x_2
x2 的过程。
class Solution { public: int mySqrt(int x) { if (x == 0) { return 0; } double C = x, x0 = x; while (true) { double xi = 0.5 * (x0 + C / x0); if (fabs(x0 - xi) < 1e-7) { break; } x0 = xi; } return int(x0); } };
参考:
https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。