LeetCode367 Valid Perfect Square

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

1
2
Input: 16
Returns: True

思路

判断一个数是否是完全平方数。

和这题LeetCode69 Sqrt(x)几乎一模一样。

只需在返回的时候判断二分搜索出来的答案,其平方之后还会不会与num相等即可。复杂度$\mathcal{O}(logn)$


还有一种解法是,根据奇数和通项公式:$1+3+5+ \cdots + (2n-1) = n^2$ ,把num每次 -1、-3、-5…,看最后能否正好减到零。复杂度$\mathcal{O}(\sqrt n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
bool isPerfectSquare(int num) {
long long l = 0, r = num, m;
while (l < r) {
m = l + (r - l + 1) / 2;
if (m * m <= num) l = m;
else r = m - 1;
}
return l * l == num;
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isPerfectSquare(int num) {
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
};
分享到 评论