leetcode:367. 有效的完全平方数

367. 有效的完全平方数

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/valid-perfect-square/

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
1
2

示例 2：

输入：num = 14
输出：false
1
2

提示：

• 0 <= x <= $2^{31}-1$

解法

• 库函数：这种一般解题的话不让用库函数
• 循环：从1开始训练遍历，求n*n与num的关系
• 二分法：通过二分法加速遍历寻找,如果找到就返回True，没有找到就返回False
• 牛顿法：数学公式推导最逼近的那个值，看看值的平方是否与num相等；
  这里不用完全遍历，遍历一半即可num/2, 当num>=2时候；
  

代码实现

库函数 sqrt

python实现

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return sqrt(num) == int(sqrt(num))
1
2
3

c++实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        return sqrt(num) == int(sqrt(num));
    }
};
1
2
3
4
5
6

遍历

python实现

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num <= 1:
            return True
        
        for i in range(num//2+1):
            if i * i == num:
                return True
            if i * i > num:
                return False
        return False
1
2
3
4
5
6
7
8
9
10
11

c++实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num <= 1) return true;
        for(long i=2; i<num/2+1; i++) {
            if (i*i == num) return true;
            else if (i*i > num) return false;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

• 时间复杂度： $O(N)$
• 空间复杂度： $O(1)$

---

二分法

python实现

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num <= 1:
            return True
        left = 0
        right = num // 2
        while left <= right:  # 注意这里是<=
            mid = left + (right-left)//2
            if mid * mid == num:
                return True
            elif mid * mid < num:
                left = mid + 1
            elif mid * mid > num:
                right = mid - 1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

c++实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num <= 1) return true;
        int left = 0;
        int right = num/2;
        while (left <= right) {
            float mid = left + (right-left) / 2;
            if (mid == num / mid) return true;
            else if (mid > num/mid) right = mid - 1;
            else if (mid < num/mid) left = mid+1;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

• 时间复杂度： $O(logN)$
• 空间复杂度： $O(1)$

---

牛顿法

• python实现

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num <= 1:
            return True
        
        x0 = num
        while 1:
            x1 = 1/2 * (x0 + num/x0)
            if abs(x0-x1) < 1e-7:
                break
            x0 = x1
        x0 = int(x1)
        return x0*x0 == num
1
2
3
4
5
6
7
8
9
10
11
12
13

• c++实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num <= 1) return true;
        float x0 = num;
        while (1) {
            int x1 = 0.5 * (x0 + num/x0);
            if (x0-x1 < 1e-6)
                break;
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

• 时间复杂度： $O(logN)$ , 但还是比二分法要快
• 空间复杂度： $O(1)$

参考

• https://leetcode.cn/problems/valid-perfect-square/solution/you-xiao-de-wan-quan-ping-fang-shu-by-le-wkee/