一棒搜、題目
LeetCode-367. 有效的完全平方數(shù)
鏈接：https://leetcode-cn.com/problems/valid-perfect-square/
難度：簡單
給定一個 正整數(shù) num 薇溃，編寫一個函數(shù)，如果 num 是一個完全平方數(shù)享扔，則返回 true ，否則返回 false 。
進(jìn)階：不要 使用任何內(nèi)置的庫函數(shù)坝茎，如 sqrt 。
示例 1：
輸入：num = 16
輸出：true
示例 2：
輸入：num = 14
輸出：false
提示：
1 <= num <= 2^31 - 1
二暇番、解題思路
該題與一起學(xué)算法-69. x 的平方根非常類似嗤放，題目的解可能存在于0到num之間，我們可以通過暴力枚舉或者二分查找來找到題目的解壁酬。
三次酌、實現(xiàn)過程
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;
};
四恨课、小結(jié)
- 時間復(fù)雜度：O(logN)，其中N是num的大小
- 空間復(fù)雜度：O(1)
