0367._valid_perfect_square.md

367. Valid Perfect Square

难度: Easy

刷题内容

原题连接

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

内容描述

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

解题方案

思路 1 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

从0开始试，不行就加1，直到相等返回True，或者大于num了返回False

beats 42.66%

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        res = 0
        while res * res <= num:
            if res * res == num:
                return True
            res += 1
        return False              

思路 2 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

牛顿法

可以看看leetcode 第69题

beats 96.64%

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        t = num
        while t * t > num:
            t = (t + num / t) / 2
        return t * t == num

思路 3 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

等差数列法

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