【LeetCode】有效的完全平方数 Java 题解

关注

发布于: 2 小时前

题目描述

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

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

示例 1：
输入：num = 16输出：true
示例 2：
输入：num = 14输出：false 
提示：
1 <= num <= 2^31 - 1

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-perfect-square著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是数学类题目，题目需要求解的是完全平方数。
首先，我们需要理解什么是完全平方数？完全平方指用一个整数乘以自己例如 1 * 1，2 * 2，3 * 3 等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。完全平方数是非负数，而一个完全平方数的项有两个。
理解了完全平方数的定义，我们首先可以使用系统函数 sqrt 函数求解。
除了使用 Math 系统函数，二分查找也比较适合这个题目，我们使用通用的二分查找即可。这里需要注意的是 mid * mid 可能超出 int 的范围，我们可以使用 long 来记录 mid * mid。避免溢出。具体实现代码如下：
这个题目还有一种好的解法是牛顿迭代法。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。没有写具体实现，感兴趣的话，可以自行搜索查找。

通过代码

sqrt 函数解法

    public boolean isPerfectSquare(int num) {        int x = (int) Math.sqrt(num);        return x * x == num;    }

复制代码

二分解法

class Solution {    public boolean isPerfectSquare(int num) {        int left = 0;        int right = num;        while (left <= right) {            int mid = left + (right - left) / 2;            long temp = (long) mid * mid;            if (temp > num) {                right = mid - 1;            } else if (temp < num) {                left = mid + 1;            } else {                return true;            }        }
        return false;    }}

复制代码

总结

二分查找算法的时间复杂度是 O(log n), 空间复杂度是 O(1)
坚持算法每日一题，加油！

发布于: 2 小时前阅读数: 8

原文链接:【http://xie.infoq.cn/article/d610fb38dbf4836cfeeca3286】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】有效的完全平方数 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论