LeetCode #367 有效的完全平方数

Problem Description

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

note

不要使用任何内置的库函数，如：sqrt。

e.g.

• 示例 1：
  • 输入：16
  • 输出：True
• 示例 2：
  • 输入：14
  • 输出：False

Solution

暴力法

可以无限优化的方法，其优化的核心就在于循环的起始和终止，效率很低不考虑。

根区间&二分法

1. Java 里 int 的最大值是 0x7fffffff，也就是 1³²-1（2147483647），大约 21 亿。最大值的平方根约等于 46340。那我不是根据整数的位数来得到一个计算的区间，这样不是能有效缩小循环的次数了吗？
2. 比如 1 位数和 2 位数[10, 99]，平方根一定是落在[1, 10)，比如 3 位数[100, 999]，平方根一定是落在[10, 32)，比如 4 位数[1000, 9999]，平方根一定是落在[31, 100)；
3. 当这个数很大的话（最大为 2147483647），相应的区间也会变大，但是区间最大的反而是 9 位数，因为 10 位数最大只到 2147483647；
4. 我们根据整数的长度取得平方根的区间后可以根据二分查找法，将平均时间复杂度降低。

class Solution {
    public static boolean isPerfectSquare(int num) {
        int[] se = interval(String.valueOf(num).length());
        int left = se[0];
        int right = se[1];
        while (true) {
            int mid = left + (right - left) / 2;
            if (mid * mid < num) {
                if (right - left == 1) {
                    return false;
                } else {
                    left = mid;
                }
            } else if (mid * mid == num) {
                return true;
            } else {
                if (right - left == 1) {
                    return false;
                } else {
                    right = mid;
                }
            }
        }
    }

    public static int[] interval(int len) {
        int start;
        int end;
        switch (len) {
            case 3:
                start = 10;
                end = 32;
                break;
            case 4:
                start = 31;
                end = 100;
                break;
            case 5:
                start = 100;
                end = 317;
                break;
            case 6:
                start = 316;
                end = 1000;
                break;
            case 7:
                start = 1000;
                end = 3163;
                break;
            case 8:
                start = 3162;
                end = 10000;
                break;
            case 9:
                start = 10000;
                end = 31623;
                break;
            case 10:
                start = 31622;
                end = 46341;
                break;
            default:
                start = 1;
                end = 10;
        }
        return new int[]{start, end};
    }
}
​

二分法有一个很需要注意的点：就是求中间值的计算公式。一般最好不要直接这样做：(left + right) / 2，因为很有可能在 left + right 的过程中就溢出了，算出来是负数的。改成 long 类型或者这样算：left + (right - left) / 2。

两个点优化之后，即使一个很大的数字也不需要经过几次的查找便可知道是否是完全平方数。以上算法的时间复杂度为 O(1) + O(log₂n) = O(log₂n)。