Valid Perfect Square
给一个n, 返回true 如果n是完美的平方数. 这个题注意的是n也许是Integer.MAX_VALUE, 所以要防止溢出, 用二叉搜索做.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public boolean isPerfectSquare(int n) { if(n <= 0) return false; if(n == 1) return true; int l = 1; int r = n; while(l <= r) { int m = l + (r - l) / 2; if(m == n / m) // m*m is overflow return n % m == 0; else if(m < n / m) l = m + 1; else r = m - 1; } return false; } } |