Daily LeetCode 367. Valid Perfect Square

https://leetcode.com/problems/valid-perfect-square/

Easy

问题描述：

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:

Input: 16
Output: true

Example 2:

Input: 14
Output: false

题目分析及代码：

给定一个正数，需要判断这个正数是不是一个完全平方数。不能调用sqrt方法

思路1:

要想知道这个正数num是不是完全平方，我们只需要计算1~num的平方，看它是不是与num相等即可，为了提高查找的效率，我们用二分查找的方式来判断：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 0, num
        
        while right >= left:
            mid = left + (right - left) // 2
            if mid**2 == num:
                return True
            elif mid**2 < num:
                left = mid + 1
            else:
                right = mid - 1
                
        return False

Ps.二分查找mid取值时使用left+(right - left)//2可以避免整数溢出的问题。

思路2:

所有的完全平方数都能够转换为奇数列的和：$n=1+3+5+…+(2n-1)$

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
          num -= i
          i += 2
        
        return num == 0

思路3: 牛顿迭代法

令$f(x) = x^2-a$，$f^{‘}(x)=2x$，牛顿迭代式为：
$$
x_{n+1}=x_n - \frac{x^2_n - a}{2x_n} = \frac{1}{2}(x_n + \frac{a}{x_n})
$$

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        r = num
        
        while r*r > num:
            r = (r + num/r) // 2
            
        return r*r == num