给定一个正整数num,编写一个函数,如果num是一个完全平方数,则返回True,否则返回False。这时候我们应该怎么做?今天小编带大家了解一下,有需要的可以参考参考。

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

给定一个正整数 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如何判断是否为有效的完全平方数的详细内容,更多请关注811轩轩资源网其它相关文章!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注