367.有效的完全平方數(shù)：
給定一個 正整數(shù) num ，編寫一個函數(shù)伏钠，如果 num 是一個完全平方數(shù)横漏，則返回 true ，否則返回 false 熟掂。
進階：不要 使用任何內(nèi)置的庫函數(shù)缎浇，如 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. 有效的完全平方數(shù) - 力扣（LeetCode）
示例 1:
輸入：num = 16
輸出：true
示例 2:
輸入：num = 14
輸出：false
提示：
1 <= num <= 2^31 - 1
初步思考：（sqrt函數(shù)）
利用內(nèi)置的平方根庫函數(shù)sqrt可以實現(xiàn)對輸入值的開方操作赴肚，進而可以快速判斷是否為有效的完全平方數(shù)素跺。
class Solution {
public:
bool isPerfectSquare(int num) {
int x = (int) sqrt(num);
return x * x == num;
}
};
進一步思考：（枚舉）
題目的進階要求是不利用內(nèi)置的庫函數(shù)二蓝。那么，我們自然而然的可以利用最為簡單的暴力枚舉法進行求解指厌。
暴力枚舉：
從1開始進行遍歷刊愚，逐一判斷其是否為num的平方根，直至出現(xiàn)某個數(shù)的平方大于num踩验。若此時仍未找到平方根鸥诽，則說明不存在完全平方數(shù)。
class Solution {
public:
bool isPerfectSquare(int num) {
int x = 1, square = 1;
while (square <= num) {
if (square == num) {
return true; //若判斷成功箕憾，則返回真牡借，結(jié)束循環(huán)
}
++x;
square = x * x;
}
return false; //若循環(huán)結(jié)束仍未找到符合條件的x，說明不是完全平方數(shù)袭异，返回假
}
};
二分查找：
優(yōu)化暴力枚舉钠龙，我們自然而然可以想到使用二分查找的方法，該題的與LeetCode69題十分相似扁远，所用的思想也是相同的俊鱼。
LeetCode69:69. x 的平方根 - 力扣（LeetCode）
下面給出了二分查找法解決該問題的完整代碼刻像，可以直接進行測試畅买。
#include<iostream>
using namespace std;
class Solution {
public:
//求x的是否為完全平方數(shù)
//左開右開
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;
}
深度思考：（數(shù)學(xué)方法）
LeetCode官方題解中給出了類似于69題中的數(shù)學(xué)方法，即使用牛頓迭代法進行問題的求解细睡。
牛頓迭代法：牛頓迭代法是一種近似求解方程（近似求解函數(shù)零點）的方法谷羞。其本質(zhì)是借助泰勒級數(shù)，從初始值開始快速向函數(shù)零點逼近溜徙。
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的官方題解湃缎，由于使用的數(shù)學(xué)方法，所以不多加介紹蠢壹。
后續(xù)也會堅持更新我的LeetCode刷題筆記嗓违，歡迎大家關(guān)注我，一起學(xué)習(xí)图贸。
