LeetCode_367. 有效的完全平方数
题目描述
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。不能使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
提示：1 <= num <= 231 - 1
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-perfect-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析
思路1：暴力枚举
最常想到的就是这种方法，从1开始逐个判断，当前数字的平方是否为num，是就停止，不是就继续。
时间复杂度：O(√n)
思路2：二分法
这种思路与x的平方根一题的思路有异曲同工之妙，跳转链接：LeetCode_69. x 的平方根_小白麋鹿的博客-CSDN博客
求x的平方根是在1至x的范围内不断二分，将mid*mid的值与x进行比较。这里判断一个数是否为完全平方数的思路大体一致，是在1至num的范围内不断二分的一个过程，如果mid*mid等于num，就说明num是一个完全平方数，否则就继续二分，直到二分结束（即left>right的时候）。
时间复杂度：O(logN)
我的题解
class Solution {
public:bool isPerfectSquare(int num) {//二分法long long left = 0, right = num, mid = 0;while(left <= right){mid = (left + right + 1) / 2;if(mid * mid > num)right = mid - 1;else if(mid * mid < num)left = mid + 1;elsereturn true;}return false;}
};