• 技术文章 >后端开发 >PHP问题

    PHP如何判断是否为有效的完全平方数

    醉折花枝作酒筹醉折花枝作酒筹2021-07-13 19:20:44原创110
    给定一个正整数num,编写一个函数,如果num是一个完全平方数,则返回True,否则返回False。这时候我们应该怎么做?今天小编带大家了解一下,有需要的可以参考参考。

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

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

    示例 1:

    输入:16
    输出:True

    示例 2:

    输入:14
    输出:False

    解题思路 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;
        }}

    推荐学习:php视频教程

    以上就是PHP如何判断是否为有效的完全平方数的详细内容,更多请关注php中文网其它相关文章!

    声明:本文原创发布php中文网,转载请注明出处,感谢您的尊重!如有疑问,请联系admin@php.cn处理
    专题推荐:PHP
    上一篇:PHP如何实现字符串相加 下一篇:php怎么去掉右边空格
    第16期线上培训班

    相关文章推荐

    • php怎么获取当前类的方法名• PHP如何求解三数之和问题• php怎么设置文件大小限制• php怎么给数组增加值• PHP如何实现字符串相加

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网