題目:

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.

給定一數,判斷它是否是完全平方數,過程不能使用開平方根的內建函數

這題還蠻像69.的
透過二分搜去找平方根

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l=1
        r=num
        while l+1!=r:
            mid=(l+r)//2
            if mid*mid==num:
                return True
            if mid*mid>num:
                r=mid
            if mid*mid<num:
                l=mid
        return False

在1~num的範圍進行二分搜
設下限l=1跟上限r=num,mid定義為(1+r)//2
mid平方大於x,r降低到mid
mid平方小於x,l提高到mid
一旦mid平方等於x就回傳True
直到l和r相鄰,若mid平方都不等於num
則num的平方根不為整數,回傳False
最後執行時間28ms(faster than 96.71%)

那我們下題見