LeetCode367-有效的完全平方数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/valid-perfect-square/

中文链接：https://leetcode-cn.com/problems/valid-perfect-square/

题目详述

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

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

示例 1：

1
2
输入：16
输出：True

示例 2：

1
2
输入：14
输出：False

题目详解

与 LeetCode69-x的平方根 是类似的思想，可以运用二分查找，也可以运用牛顿迭代法。

方法一：二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00367 {

    public boolean isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l < r) {
            int mid = l + r >>> 1;
            if ((long) mid * mid >= num) r = mid;
            else l = mid + 1;
        }
        return r * r == num;
    }
}

方法二：牛顿迭代法。

1
2
3
4
5
6
7
8
9
10
public class LeetCode_00367 {

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