java数据结构与算法刷题-----LeetCode367. 有效的完全平方数

本文主要是介绍java数据结构与算法刷题-----LeetCode367. 有效的完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

文章目录

- 自实现Math.sqrt()函数：牛顿迭代法

`自实现Math.sqrt()函数：牛顿迭代法`

解题思路：时间复杂度O( $log_2n$ )，空间复杂度O( $1$ )

本题如果想着暴力求解，找到平方根一定会超时
如果用二分法，就不会超时，但是这个方法无法精确求出根（精度不够）
但是如果使用牛顿迭代法，可以在找到一个数字的n次方根无限近似值（高数微积分中的泰勒级数，微积分本身就是干这个的，求极限，将曲线划分为若干小的块，对每个块求积分，最后得到无限趋近于正确结果的值）。
这道题和69题是一样的。具体如何做，可以参考69题

🏆LeetCode69：x 的平方根(二分查找和数学共有题)`https://blog.csdn.net/grd_java/article/details/125511772`

代码

二分法：如果理解不了牛顿迭代法，最起码要会这个

class Solution {public boolean isPerfectSquare(int num) {int left = 0, right = num/2+1;//二分范围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 = (cur+num/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说明是完全平方根}
}