367.有效的完全平方数：
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
- Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Follow up: Do not use any built-in library function such as sqrt.
题目链接：367. 有效的完全平方数 - 力扣（LeetCode）
示例 1:
输入：num = 16
输出：true
示例 2:
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
初步思考：（sqrt函数）
利用内置的平方根库函数sqrt可以实现对输入值的开方操作，进而可以快速判断是否为有效的完全平方数。
class Solution {
public:
bool isPerfectSquare(int num) {
int x = (int) sqrt(num);
return x * x == num;
}
};
进一步思考：（枚举）
题目的进阶要求是不利用内置的库函数。那么，我们自然而然的可以利用最为简单的暴力枚举法进行求解。
暴力枚举：
从1开始进行遍历，逐一判断其是否为num的平方根，直至出现某个数的平方大于num。若此时仍未找到平方根，则说明不存在完全平方数。
class Solution {
public:
bool isPerfectSquare(int num) {
int x = 1, square = 1;
while (square <= num) {
if (square == num) {
return true; //若判断成功，则返回真，结束循环
}
++x;
square = x * x;
}
return false; //若循环结束仍未找到符合条件的x，说明不是完全平方数，返回假
}
};
二分查找：
优化暴力枚举，我们自然而然可以想到使用二分查找的方法，该题的与LeetCode69题十分相似，所用的思想也是相同的。
LeetCode69:69. x 的平方根 - 力扣（LeetCode）
下面给出了二分查找法解决该问题的完整代码，可以直接进行测试。
#include<iostream>
using namespace std;
class Solution {
public:
//求x的是否为完全平方数
//左开右开
bool isPerfectSquare(int x) {
int left = 0;//考虑0的情况
int right = x / 2+2; //考虑1的情况
while (left + 1 != right)
{
int mid = left + (right - left) / 2;
if (mid*mid < x) //使用除法避免溢出（乘法会溢出）
{
left = mid;
}
else if(mid*mid>x)
{
right = mid;
}
else
{
return true;
}
}
return false;
}
};
int main()
{
Solution C;
bool out = C.isPerfectSquare(13);
cout << out << endl;
return 0;
}
深度思考：（数学方法）
LeetCode官方题解中给出了类似于69题中的数学方法，即使用牛顿迭代法进行问题的求解。
牛顿迭代法：牛顿迭代法是一种近似求解方程（近似求解函数零点）的方法。其本质是借助泰勒级数，从初始值开始快速向函数零点逼近。
class Solution {
public:
bool isPerfectSquare(int num) {
double x0 = num;
while (true) {
double x1 = (x0 + num / x0) / 2;
if (x0 - x1 < 1e-6) {
break;
}
x0 = x1;
}
int x = (int) x0;
return x * x == num;
}
};
这部分代码参考的是LeetCode的官方题解，由于使用的数学方法，所以不多加介绍。
后续也会坚持更新我的LeetCode刷题笔记，欢迎大家关注我，一起学习。
