LeetCode #367 有效的完全平方数

本贴最后更新于 1560 天前,其中的信息可能已经时移世易

367.png

Problem Description

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

note

不要使用任何内置的库函数,如:sqrt

e.g.

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

Solution

暴力法

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

根区间&二分法

  1. Java 里 int 的最大值是 0x7fffffff,也就是 132-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(log2n) = O(log2n)。

  • 算法
    428 引用 • 254 回帖 • 24 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 二分查找
    4 引用 • 21 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...