首页 > 代码库 > [leetcode]Sqrt(x)
[leetcode]Sqrt(x)
Sqrt(x)
Implement
int sqrt(int x).Compute and return the square root of x.
【注意】：
1. 本题int类型可能会溢出，因此不能用乘法运算，应尽量用除法。
2. 绝大多数数字都不是可开方的，该如何得到比较近的结果呢？
算法思路：
思路1：顺序遍历肯定不需要试了，二分查找比较靠谱。二分法在数值计算中非常常见，需要熟练掌握。
代码如下：
public class Solution { public int sqrt(int x) { if(x <= 1) return x == 0 ? 0 : x; int l = 1, r = x /2 + 1 ; while(l <= r){ int mid = (l + r) / 2; if(mid <= x / mid && (mid + 1) > x / (mid + 1)){ return mid;//这里用的很巧妙 }else if(mid > x / mid){ r = mid - 1; }else{ l = mid + 1; } } return 0; }}
思路2：牛顿迭代法；比较高大上，详细分析过程请戳这里。
代码如下：
1 public int sqrt(int x) { 2 if (x == 0) return 0; 3 double lastY = 0; 4 double y = 1; 5 while (y != lastY) 6 { 7 lastY = y; 8 y = (y + x / y) / 2; 9 }10 return (int)(y);11 }
这道题出的很好
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。