一、题目
LeetCode-367. 有效的完全平方数
链接：https://leetcode-cn.com/problems/valid-perfect-square/
难度：简单
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
二、解题思路
该题与一起学算法-69. x 的平方根非常类似，题目的解可能存在于0到num之间，我们可以通过暴力枚举或者二分查找来找到题目的解。
三、实现过程
c++
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 0,right = num;
while(left <= right){
long mid = (left + right) / 2;
if(mid*mid == num){
return true;
}else if(mid*mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
};
PHP
class Solution {
/**
* @param Integer $num
* @return Boolean
*/
function isPerfectSquare($num) {
$left = 0;
$right = $num;
while($left <= $right){
$mid = (int)(($left + $right) / 2);
if($mid*$mid == $num){
return true;
}else if($mid*$mid < $num){
$left = $mid + 1;
}else{
$right = $mid - 1;
}
}
return false;
}
}
JavaScript
/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function(num) {
var left = 0,right = num,mid;
while(left <= right){
mid = Math.floor((left + right) / 2);
if(mid*mid == num){
return true;
}else if(mid*mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
};
四、小结
- 时间复杂度：O(logN)，其中N是num的大小
- 空间复杂度：O(1)
