367. Valid Perfect Square

今天我們一起挑戰leetcode第367題Valid Perfect Square!

題目

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

Example 1:
Input: num = 16
Output: true

Example 2:
Input: num = 14
Output: false

今天這題與我們昨天做過的sqrt(x)具有相關性，可以利用昨天寫出來的程式碼，來完成這題的要求。此題會給我們一整數，並要我們回傳此數是否為完全平方數，是就回傳True否則False。當然這題與昨天一樣，題目要求不能使用內建的sqrt功能。

修改sqrt功能

我們可以參考昨天曾經實作過的sqrt功能，但與昨天不同，我們並非要求出某個數的根號取到整數，我們是要直接確認某數是否為完全平方數，意味著在我們找到題目給我們數的根號的範圍時，要確認的是其是否為整數。

以下是python的程式碼

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        guess = 1000
        while True:
            p = int(guess)
            q = p + 1
            guess = (guess + num / guess) / 2
            if p*p == num:  # 確認是完全平方數
                return True
            if p*p <= num and q*q > num:  # 非完全平方數，因其根號介於兩整數之間
                return False