文章目录
- 一、读题
- 二、算法思路
- 三、代码实现：
一、读题
题目来源：https://leetcode.cn/problems/valid-perfect-square/
题目很简单，就是判断一个数是不是完全平方数，是就返回true，不是就返回false，主包就喜欢这种第一眼就可以理解的题目哈哈哈
二、算法思路
方法一：这个题目本质也还是暴力题，判断一个数是不是完全平方数，那很简单啊，遍历嘛，从1开始遍历，直到等于num，如果找不到就说明没有，如果找到中途就直接返回结果。时间复杂度是O(n)的。
方法二：其实是方法一的优化版，我们使用二分查找可以对这个遍历的过程进行优化，每一次的二分查找结果都和num进行比较，当然了二分查找相信各位佬都是手拿把掐的，主包就不献丑了哈，可以直接看代码。时间复杂度可以优化为O(logn)的。
方法三：这个方法是一个数学方法，我们使用奇数从1开始相加，如果最终相加能够得到num，那么说明num就是完全平方数。例：4 = 1 + 3 ，9 = 1 + 3 + 5，16 = 1 + 3 + 5 + 7；时间复杂度是O(n)
原理是什么呢？不知道大家还记不记得高中学的等差数列求和，这个原理 就是根据等差数列得到的，大家可以不必要知道原理是什么，会算就可以了，有兴趣的可以继续看主包讲解，没有兴趣的可以直接看代码
16 = 1 + 3 + 5 + 7 推导得出 ：S=1+3+5+7 … +(2n - 3) +(2n-1)
这个是奇数相加，我们可以直观的看出来两数之间的差是2，那说明这是一个公差为2的等差数列
等差数列求和的公式是:(首项+末项)*项数 /2
首项:1
末项 :(2n-1)
项数:n
(假设当前我的最后一项是15，那么对应就是1，3，5，7，9，11，13，15，15=(2n-1)那么n就等于8，所以项数就是8)
代入公式就得:(1 + 2n - 1) * n / 2 = n^2
说明奇数相加的结果一定是偶数，并且是一个完全平方数
验算:当n=8的时候，平方数是64，1+3+5+7 +9 +11 +13 + 15=64,
三、代码实现：
public boolean isPerfectSquare(int num) { //方法二：遍历，二分优化 ，方法一就不写了，相信大家都会 if (num == 0 || num == 1) return true; int left = 0; int right = num / 2; while (left <= right) { int mid = (right - left) / 2 + left; long ans = (long) mid * mid; if (num == ans) { return true; } else if (num > ans) { left = mid + 1; } else { right = mid - 1; } } return false; } }class Solution { public boolean isPerfectSquare1(int num) { //方法三：数学思路，完全平方数一定是可以由不同的奇数组合而成（从1开始逐渐增大的奇数） int ans = 1; while (num > 0) { num -= ans; ans += 2; } // System.out.println(num); return num == 0; }各位佬，如果有什么更加高效的算法欢迎评论区讨论，指导一下主包进步，原诸君共勉
