7/1 每日一題 (找出完全平方數)

 Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

 

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

 

Constraints:

• 1 <= num <= 231 - 1

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num ==1:
            return True

        
        n_l=1 #左指針
        n_r=num//2 #右指針
        mid_sqrt= ((n_l+n_r)//2)**2
        while n_l <= n_r:
            if n_l **2 == num or n_r **2 == num :
                return True
            if mid_sqrt < num:
                n_l=(n_l+n_r)//2
                n_r -=1
            
            else:
                n_r=(n_l+n_r)//2
                n_l += 1
            
            mid_sqrt= ((n_l+n_r)//2)**2
        
        return n_l **2 ==num  

-----------------------參考答案

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


-------------
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num==1:
            return True
        else:
            l=0
            r=num
            while l<r:
                mid=(l+r)//2 #檢查中間值的平方
                sqrt=mid**2
                if sqrt == num: 
                    return True
                elif sqrt > num: #mid**2 大於目標 所以範圍向左移動 ,右指針移到mid
                    r = mid
                else:            #mid**2 小於目標 所以範圍向右移動, 左指針移到mid+1
                    l=mid+1  
            return False