解題思路：
該題可以用三種方法解決，第一種就是呼叫庫函式，直接sqrt找到，代碼如下：
class Solution {
public:
bool isPerfectSquare(int num) {
int mid = (int)sqrt(1.0 * num);
return mid * mid == num ? true : false;
}
};
暴力的方法也不是不可以，但是太消耗記憶體和時間了，代碼如下：
class Solution {
public:
bool isPerfectSquare(int num) {
long x = 1, square = 1;
while (square <= num) {
if (square == num) {
return true;
}
++x;
square = x * x;
}
return false;
}
};
最后就是最實用的二分法，通過不斷取中間值，判斷是否平方能成為num，代碼如下：
class Solution {
public:
bool isPerfectSquare(int num) {
int low = 1, high = num;
while(low <= high) {
// 防止溢位
int mid = (high - low) / 2 + low;
// 用除的方法而不是乘，也是防止溢位
int div = num / mid;
if(div == mid) {
// 可以整除
if(num % mid == 0) {
return true;
}
// 那么mid就小了點
low = mid + 1;
}
// mid大了，high放小一點
if(div < mid) {
high = mid - 1;
} else {// mid小了，low放大一點
low = mid + 1;
}
}
return false;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348292.html
標籤：其他