Valid Perfect Square

Posted on | In , |

经典的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isPerfectSquare (int num){
  if (num < 1) return false; //0为啥不算？
  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 isPerfectSquare (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 isPerfectSquare(int num){
  int i=1;
  while (num > 0){
    num -= i;
    i += 2;
  }
  return num == 0;
}