题目大意
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
示例1：
输入：16
输出：True
示例2：
输入：14
输出：False
方法一：二分法
首先打表，存储int范围内的所有完全平方数，然后对表进行二分查找。
public boolean isPerfectSquare(int num) {
int[] square = new int[((int)Math.sqrt(Integer.MAX_VALUE))+1];
for(int i=0;i<square.length;i++)
square[i] = i*i;
int low = 0, high = square.length-1;
while(low<high) {
int mid = low + (high-low)/2;
if(square[mid] == num) return true;
else if(square[mid] < num)
low = mid + 1;
else
high = mid - 1;
}
return square[low] == num;
}
运行时间4ms,击败14.13%。
方法三：暴力迭代 超时
迭代的方法，依次尝试，这题会超时。
public boolean isPerfectSquare(int num) {
int i=0;
while(i*i<num)
i++;
return i*i==num;
}
方法三：公式法
2^n = 1 + 3 + 5 +...+ 2*k-1
public boolean isPerfectSquare(int num) {
int i=1;
while(num>0) {
num -= i;
i+=2;
}
return num == 0;
}
方法四：牛顿迭代法
image.png
因为此题求x^2 = n。构造函数f(x) = x^2 - n。
f'(x) = 2x.
public boolean isPerfectSquare(int num) {
int r = num;
while((double)r*r > num)
r = (r + num/r)/2;
return r*r ==num;
}
运行时间0ms,击败100%。
