企业做网站设计的,余姚做企业网站,免费个人简历制作网站,发帖推广平台java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 自实现Math.sqrt()函数#xff1a;牛顿迭代法 自实现Math.sqrt(…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 自实现Math.sqrt()函数牛顿迭代法 自实现Math.sqrt()函数牛顿迭代法
解题思路时间复杂度O( l o g 2 n log_2n log2n)空间复杂度O( 1 1 1) 本题如果想着暴力求解找到平方根一定会超时如果用二分法就不会超时但是这个方法无法精确求出根精度不够但是如果使用牛顿迭代法可以在找到一个数字的n次方根无限近似值高数微积分中的泰勒级数微积分本身就是干这个的求极限将曲线划分为若干小的块对每个块求积分最后得到无限趋近于正确结果的值。这道题和69题是一样的。具体如何做可以参考69题 LeetCode69x 的平方根(二分查找和数学共有题)https://blog.csdn.net/grd_java/article/details/125511772
代码 二分法如果理解不了牛顿迭代法最起码要会这个 class Solution {public boolean isPerfectSquare(int num) {int left 0, right num/21;//二分范围while (left right) {int mid (right - left) / 2 left;long square (long) mid * mid;//获取mid平方if (square num) {//如果比num小说明mid太小了left mid 1;//去mid右边} else if (square num) {//比num大说明mid太大right mid - 1;//去mid左边} else {return true;//如果和num一样就找到了其完全平方根}}return false;}
}牛顿迭代法我们不需要求出平方根精确值只需要获取其平方根整数形式如果和num一样就是完全平方根因为完全平方根是整数 class Solution {public boolean isPerfectSquare(int num) {double cur num,pre num;//当前迭代结果上次迭代结果while (true) {//公式cur num/cur/2cur (curnum/cur)*0.5;// if (pre - cur 1e-6) break;确定精度两次迭代结果的差的绝对值指定精度就说明精度到位if(Math.abs(pre-cur) 1e-7) break;pre cur;//pre记录cur的结果成为下一次的前驱结果}int x (int) cur;//获取迭代结果的整数形式也就是(int)Math.sqrt(num)return x * x num;//如果平方为num说明是完全平方根}
}
