Implementint sqrt(int x).
Compute and return the square root of x.
这道题目直接调用Math.sqrt(x)也可以AC，但是我们最好用二分查找或者牛顿迭代法来进行查找。
牛顿迭代法是通过切线来确定根的位置，通过无限趋近的极限思想来找平方根，证明省略，我们直接使用结论。
x[i+1]=x[i]/2+n/(2*x[i]);
当x[i+1]趋近于x[i]时，x[i]即为要求的解
public int sqrt(int x) {
if (x == 0) return 0;
double pre = 0;
double cur = 1;
while (Math.abs(cur - pre) > 0.001) {
pre = cur;
cur = pre / 2 + x / (2 * pre);
}
return (int) cur;
}
问题描述 Implementint sqrt(int x).Compute and return the squa...
https://leetcode-cn.com/problems/sqrtx/
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sqrtx ...
链接 https://leetcode-cn.com/problems/sqrtx/description/ 要求...
https://leetcode-cn.com/problems/sqrtx/submissions/[https...
题目地址 https://leetcode.com/problems/sqrtx/description/[htt...
2021-05-03 LeetCode每日一题 链接：https://leetcode-cn.com/proble...
2021-05-01 LeetCode 每日一题 链接：https://leetcode-cn.com/probl...
2021-05-02 LeetCode每日一题 链接：https://leetcode-cn.com/proble...
2021-04-30 LeetCode每日一题 链接：https://leetcode-cn.com/proble...
本文标题：LeetCode每日一题：sqrtx
本文链接：https://www.haomeiwen.com/subject/jlntfxtx.html
网友评论