LeetCode 367. 有效的完全平方数

367. 有效的完全平方数

题目：给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
链接 https://leetcode.cn/problems/valid-perfect-square

个人思路

1. 简单题，先直接开方（回家等通知做法

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if int(num ** (1/2)) == num ** (1/2):
            return True
        else:
            return False
1
2
3
4
5
6

还挺快

官方是判断是否为整数：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return float.is_integer(pow(num, 0.5))
1
2
3

复杂度分析
代码中使用的pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。

2. 二分法

记得取整是’//'，

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 1
        # 先提前除以2，因为num / 2已经大于等于num的完全平方数
        # 因为还有个1比较特殊，所以还是加上1以防万一
        right = num / 2 + 1
        while left <= right:
            mid = (left + right) // 2
            sqrt = mid * mid
            if sqrt == num:
                return True
            elif sqrt > num:
                right = mid - 1
            else:
                left = mid + 1
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间和内存比上面的要差

其他思路

1. 暴力：
   思路和算法

如果num 为完全平方数，那么一定存在正整数 x 满足 x×x=num。于是我们可以从 1 开始，从小到大遍历所有正整数，寻找是否存在满足x×x=num 的正整数 xx。在遍历中，如果出现正整数 x 使 x×x>num，那么更大的正整数也不可能满足 x×x=num，不需要继续遍历了。

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = 1
        square = 1
        while square <= num:
            if square == num:
                return True
            x += 1
            square = x * x
        return False
1
2
3
4
5
6
7
8
9
10

复杂度分析
时间复杂度：O(n0.5)，其中 n 为正整数 num 的最大值。我们最多需要遍历 n0.5+1个正整数。
空间复杂度：O(1)。

2. 牛顿迭代法

牛顿迭代法是一种近似求解方程（近似求解函数零点）的方法。其本质是借助泰勒级数，从初始值开始快速向函数零点逼近。




复杂度分析：

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-perfect-square/solution/you-xiao-de-wan-quan-ping-fang-shu-by-le-wkee/

其他

1 4=1+3 9=1+3+5 16=1+3+5+7以此类推，模仿它可以使用一个while循环，不断减去一个从1开始不断增大的奇数，若最终减成了0，说明是完全平方数，否则，不是。
原理(n+1) ^ 2-n ^ 2=2n+1

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        num1 = 1
        while num > 0:
            num -= num1
            num1 += 2
        return num == 0
1
2
3
4
5
6
7

作者：lu-guo-de-feng-2
链接：https://leetcode.cn/problems/valid-perfect-square/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-c-ti-jiao-zh-44/