ValidPerfectSquare [source code]

public class ValidPerfectSquare {
static
/******************************************************************************/
public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 0) return false;
        else if (num == 1) return true;
        int lo = 1, hi = num - 1;
        while (lo <= hi) {
            int guess = lo + (hi - lo) / 2;
            double divRes = (double) num / guess;
            if (divRes == guess) break;
            else if (divRes < guess) hi = guess - 1;
            else lo = guess + 1;
        }
        int res = lo + (hi - lo) / 2;
        return (double) num / res == res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidPerfectSquare.Solution tester = new ValidPerfectSquare.Solution();
        int[] inputs = {1,2,3,4,5,15,16,32,64,10000};
        for (int i : inputs) System.out.printf("%d -> %b%n", i, tester.isPerfectSquare(i));
    }
}

这个题目总体来说还是比较简单的, 不过真正能够想到 Binary Search 也并不是那么简单. 最后的速度是0ms (40%), 估计是最优解了; 0ms (40%).

这里刚开始有一个抉择, 就是 header 用什么判断. 刚开始的想法是用类似!(num / guess == guess) || (num % guess == 0) 来完成的. 但是这个就碰到了一个类似 Binary Search 的时候的问题: 你循环内部的一个 var 用来帮助进行循环的 header 的判断. 最后认为比较好的写法就是跟 Binary Search 一样的写法, 直接用 lo 和 hi 进行判断;

这个模板也可以应用于所有其他的 Binary Search 的变形应用上面: Binary Search 最后你真正维护的就是 hi 和 lo 这两个边界, 而不是 mid 这样的中间量(虽然直接对这个 mid 进行判断来terminate 显得方便很多, 但是这样写出来的代码就丑很多);

一个小的技术细节, 关于 JAVA 里面的整数除法和浮点除法:

java> 8 == (65 / 8)  
java.lang.Boolean res0 = true  
java> int i = 8  
int i = 8  
java> double d = 65 / 8  
double d = 8.0  
java> double d = (65) / 8  
double d = 8.0  
java> double d2 = (int) 65 / 8  
double d2 = 8.0  
java> double d2 = (double) 65 / 8  
double d2 = 8.125  
java> 8 == d2  
java.lang.Boolean res4 = false  
java> 8 == d  
java.lang.Boolean res5 = true

是否能够 promote 浮点除法完全取决于两个除数里面有没有一个是浮点数, 而不取决于你 operator 本身怎么写, 也不取决于你最后的左值是什么类型(左值是 double 并不能保证除法就是浮点除法);

discussion 的最优解有很多也是用的这个做法, 不过他们习惯于这么写:

public boolean isPerfectSquare(int num) {  
  if (num < 1) return false;  
  long left = 1, right = num;// long type to avoid 2147483647 case  

  while (left <= right) {  
    long mid = left + (right - left) / 2;  
    long t = mid * mid;  
    if (t > num) {  
      right = mid - 1;  
    } else if (t < num) {  
      left = mid + 1;  
    } else {  
      return true;  
    }  
}

最后的区别在于他们是用乘法来检查, 这样就避免了检查 truncation 的问题; 注意, 这个写法要求最后 mid 用 long, 不然可能会 overflow;

这个是 discussion 上面一个有意思的代码:

public boolean isPerfectSquare(int num) {  
    int i = 1;  
    while (num > 0) {  
        num -= i;  
        i += 2;  
    }  
    return num == 0;  
}

这个依赖的原理是所有的 square 都可以表示成为1 + 3 + 5 + 7 + ...; 这个算法最后的复杂度是O(sqrt(n)):
Σ(1 + 2i) = n =>
x + 2Σi = n =>
x + 2(x(x+1)) = n =>
2x^2 + 3x = n =>
x = [-3 +/- sqrt(9 + 8n)]/4 =>
you can see that n is in a square root term, so the complexity should be O(sqrt(n)).

另外可以用 Newton Method 直接计算平方根:

public boolean isPerfectSquare(int num) {  
        long x = num;  
        while (x * x > num) {  
            x = (x + num / x) >> 1;  
        }  
        return x * x == num;  
}

Newton Method 最后计算出来的 halt 的地方是floor(sqrt(n)) , 所以最后还要专门检查一下 num 是不是perfect square;

另外可以看到:

java> 17/2  
java.lang.Integer res0 = 8  
java> 17>>1  
java.lang.Integer res1 = 8  
java> 23/4  
java.lang.Integer res6 = 5  
java> 23>>2  
java.lang.Integer res7 = 5

shift 完成的其实是跟普通的除法一样的, 带 truncate 的除法;

Problem Description

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True
Example 2:

Input: 14
Returns: False
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:38.03%
Contributor: LeetCode
Companies
linkedin
Related Topics
binary search math
Similar Questions
Sqrt(x) Sum of Square Numbers