How to determine whether it is a valid perfect square number in PHP

Given a positive integer num, write a function that returns True if num is a perfect square number, otherwise it returns False. What should we do at this time? Today, the editor will take you through it, and you can refer to it if you need it.

Given a positive integer num, write a function that returns True if num is a perfect square number, otherwise it returns False.

Note: Do not use any built-in library functions, such as sqrt.

Example 1:

输入：16
输出：True

Example 2:

输入：14
输出：False

Solution idea 1

php cannot use the pow function. The operation is ** 0.5. Multiplying by 0.5 times has the same effect as the root number starting from PHP5.6.0.

Code

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

Solution idea 2

Use the properties of perfect square numbers. A perfect square number is the sum of a series of odd numbers, for example:

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))。

Code

class Solution {
    /** 
    * @param Integer $num 
    * @return Boolean 
    */
    function isPerfectSquare($num) {
        $start = 1;
        while($num > 0)
        {
            $num -= $start;   // 累减到最后是 0 
            $start += 2;      // 每次 +2 保持是连续奇数
        }
        return $num == 0;
    }}

Problem-solving ideas 3

Binary search

Code

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;
    }}

Recommended learning:php video tutorial

The above is the detailed content of How to determine whether it is a valid perfect square number in PHP. For more information, please follow other related articles on the PHP Chinese website!