0367._valid_perfect_square.md

Navigation

• Navigation
• Links
• Solution 1 暴力法
• Solution 2 二分思想
• Solution 3 数学法，等差公式
• Solution 4 牛顿迭代法，近似求解

Links

1. https://leetcode.com/problems/valid-perfect-square/
2. https://leetcode-cn.com/problems/valid-perfect-square/

Solution 1 暴力法

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

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        i = 1

        while i * i < num:
            i += 1
        
        return i * i == num

Solution 2 二分思想

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

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left, right = 1, num

        while left < right:
            mid = (left + right) // 2
            if mid * mid < num:
                left = mid + 1
            else:
                right = mid

        return left * left == num

Solution 3 数学法，等差公式

1 + 3 + 5 + 7 + ...(2N - 1) = N ** 2。 任意一个平方数可以表示成这样的奇数序列和。

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

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        i = 1

        while num > 0:
            num -= i
            i += 2

        return num == 0

Solution 4 牛顿迭代法，近似求解

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        i = num

        while i * i > num:
            i = (i + num / i) // 2

        return i * i == num