木又连续日更第55天(55/100)
木又的第196篇leetcode解题报告
数学
类型第12篇解题报告
leetcode第367题:有效的完全平方数
https://leetcode-cn.com/problems/valid-perfect-square/
【题目】
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如 sqrt。
示例 1:
输入:16
输出:True
示例 2:
输入:14
输出:False
【思路】
最直接的方法,使用sqrt(),当然,题目明确不让使用。
那我们怎么做?
这题非常像从(0, num+1)中寻找一个是否存在一个数res,使得res*res==num。
为了提升效率,那就使用二分查找咯!
同时,我们可以考虑缩小查找的区间。
【代码】
python版本
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
if num < 2:
return True
l, r = 1, num / 2
while l <= r:
mid = (l + r) / 2
res = mid * mid
if res == num:
return True
elif res < num:
l = mid + 1
else:
r = mid - 1
return False
C++版本
class Solution {
public:
bool isPerfectSquare(int num) {
if(num == 1)
return true;
int l = 1, r = num / 2;
double mid;
// 循环结束后,r*r < num <= l*l
while(l <= r){
mid = (l + r) / 2;
if(mid * mid == num)
return true;
if(mid * mid < num)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
};
前一篇文章:T195-3的幂