valid perfect square

经典的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
public boolean (int num){
if (num < 1) return false;
long lo = 1; long hi = num; //避免 2147483647
while (lo <= hi){
long mid = (lo + hi) / 2;
long tem = mid * mid;
if (tem == num) return true;
if (tem < num) lo = mid+1;
else hi = mid-1;
}
return false;
}

牛顿迭代法

1
2
3
4
5
6
7
8
public boolean (int num){
if (num < 1) return false;
long x = num;
while (x * x > num){
x = (x + num/x) / 2;
}
return x * x == num;
}

还有个神奇的算法,完全平方数都是由 1+3+5+7…构成,所以可以写成

1
2
3
4
5
6
7
8
public boolean (int num){
int i=1;
while (num > 0){
num -= i;
i += 2;
}
return num == 0;
}