iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 18

Leetcode 挑戰 Day 18 [ 367. Valid Perfect Square ]

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

上一篇
Leetcode 挑戰 Day 17 [ 69. Sqrt(x) ]
下一篇
Leetcode 挑戰 Day 19 [ 633. Sum of Square Numbers ]
系列文
試煉之地 Leetcode 的挑戰19

尚未有邦友留言

立即登入留言