给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入：16
输出：True
示例 2：
输入：14
输出：False
C++1
思路：使用暴力遍历，只需要遍历到num的一半即可判断...时间复杂度O(n)
class Solution {
public:
bool isPerfectSquare(int num) {
if(num == 0 || num == 1){
return true;
}
long long mid = num/2;
for(long long i=1;i<=mid;i++){
if(i * i == num){
return true;
}
}
return false;
}
};
C++2
思路：使用二分法，效率快很多，时间复杂度O(logn)
class Solution {
public:
bool isPerfectSquare(int num) {
long long left = 0,right = num;
while(left<=right){
long long mid = left + (right-left)/2;
long long temp = mid * mid;
if(temp == num){
return true;
}else if(temp<num){
left = mid+1;
}else{
right = mid-1;
}
}
return false;
}
};
