每天进步一点点🤏

有效的完全平方数

  • 860 字

有效的完全平方数

题目

1
2
3
4
5
6
7
8
9
10
11
给你一个正整数 num 如果 num 是一个完全平方数,则返回 true ,否则返回 false

示例 1：
输入：num = 16
输出：true
解释：返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2：
输入：num = 14
输出：false
解释：返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
思路:
使用二分法查找,直至左右两边相等或左边大于右边

代码:
/**
 * @param Integer $num
 *
 * @return Boolean
 */
function isPerfectSquare($num)
{
    $left  = 0;
    $right = $num;
    while ($left <= $right) {
        // 取中间值
        $mid = intdiv($left + $right, 2);

        if ($mid * $mid > $num) {
            // 过大,说明在右边,mid-1,防止出现left和right相差1的死循环情况
            $right = $mid - 1;
        } elseif ($mid * $mid < $num) {
            // 过小,说明在左边,mid+1,防止出现left和right相差1的死循环情况
            $left = $mid + 1;
        } else {
            return true;
        }
    }

    return false;
}