0%

leetcode Valid Perfect Square

leetcode Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1
2
Input: 16
Returns: True

Example 2:

1
2
Input: 14
Returns: False

题目地址:leetcode Valid Perfect Square

题意:给定一个数n,要求不使用sqrt函数判断该数是否为完全平方数

思路:二分。。  L = 1 ,  R = num / 2 +1开始枚举即可。。。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isPerfectSquare(int num) {
long long L = 1, R = (num >> 1) + 1;
while (L <= R) {
long long m = L + ((R - L) >> 1);
long long mul = m * m;
if (mul == num) return true;
else if (mul > num) R = m - 1;
else L = m + 1;
}
return false;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public boolean isPerfectSquare(int num) {
long L = 1, R = (num >> 1) + 1;
while (L <= R) {
long m = L + ((R - L) >> 1);
long mul = m * m;
if (mul == num) return true;
else if (mul > num) R = m - 1;
else L = m + 1;
}
return false;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
L, R = 1, (num >> 1) + 1
while L <= R:
m = L + ((R - L) >> 1)
mul = m ** 2
if mul == num:
return True
elif mul > num:
R = m - 1
else:
L = m + 1
return False

 

本题是leetcode 367  Valid Perfect Square题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~