原文链接：何晓东 博客
无效的齐全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个齐全平方数，则返回 True，否则返回 False。
阐明：不要应用任何内置的库函数，如 sqrt。
示例 1：
输出：16 输入：True
示例 2：
输出：14 输入：False
起源：力扣（LeetCode）
链接：无效的齐全平方数
解题思路 1
php 不能应用 pow 函数，骚操作是 ** 0.5 这样的形式，自乘 0.5 次从 PHP5.6.0开始和根号成果一样。
代码
<code class="php">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))。
代码
<code class="php">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
二分查找
代码
<code class="php">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讲
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：leetcode-367PHP-判断有效的完全平方数
转载请注明原文链接：leetcode-367PHP-判断有效的完全平方数
