首页 > 代码库 > 【LeetCode】Sqrt(x) (2 solutions)
【LeetCode】Sqrt(x) (2 solutions)
Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
解法一：牛顿迭代法
求n的平方根，即求f(x)=x2-n的零点
设初始值为x0，注，不要设为0，以免出现除数为0，见后。
则过(x0,f(x0))点的切线为g(x)=f(x0)+f‘(x0)*(x-x0)
g(x)与x轴的交点为x1=x0-f(x0)/f‘(x0)
递推关系为xn+1=xn-f(xn)/f‘(xn)
当收敛时即为解。
class Solution {public: int sqrt(int x) { double x0 = 1; double xn = (x0+x/x0)/2; while(abs(x0-xn) > 1e-5) { x0 = xn; xn = (x0+x/x0)/2; } return x0; }};
解法二：二分法
注意返回为int，结果会取整。
class Solution {public: int sqrt(int x) { long long low = 0; long long high = x; long long mid; while(low <= high) { mid = (low+high)/2; long long result = mid*mid; if(result == x) return mid; else if(result > x) high = mid-1; else low = mid+1; } return high; }};
【LeetCode】Sqrt(x) (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。