关于php:leetcode-367PHP-判断有效的完全平方数

原文链接：何晓东 博客

无效的齐全平方数

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

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

示例 1：

输出：16
输入：True 

示例 2：

输出：14
输入：False 

起源：力扣（LeetCode）
链接：无效的齐全平方数

解题思路 1

php 不能应用 pow 函数，骚操作是 ** 0.5 这样的形式，自乘 0.5 次从 PHP5.6.0 开始 和根号成果一样。

代码

class Solution {

    /**
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {return $num**0.5 == (int)($num**0.5);
    }
}

解题思路 2

利用齐全平方数的性质，齐全平方数是一系列奇数之和，例如：

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
1+3+...+(2n-1) = (2n-1 + 1) n/2 = n* n

工夫复杂度为 O(sqrt(n))。

代码

class Solution {

    /**
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {
        $start = 1;
        while($num > 0)
        {
            $num -= $start;   // 累减到最初是 0 
            $start += 2;      // 每次 +2 放弃是间断奇数
        }

        return $num == 0;
    }
}

解题思路 3

二分查找

代码

class Solution {

    /**
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {
        $left = 0;
        $right = $num;
        while($left < $right)
        {$mid = $right - floor(($right-$left)/2);
            if ($mid * $mid == $num) {return true;} elseif ($mid * $mid > $num) {$right = $mid - 1;} else {$left = $mid + 1;}
        }
        return $left * $left == $num;
    }
}

参考链接: 平方数

顺带举荐 算法通关面试 40 讲