基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/valid-perfect-square/

演算法與資料結構

• Binary Search

題意

給予一個數字 num ，回傳 true 如果是個完全平方數，否則 false 。

完全平方

• https://zh.wikipedia.org/zh-tw/%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9

完全平方是指此數是另外一個「正整數」的平方

思考方式

題目是要求確認輸入的值是不是完全平方數

到二分搜尋法為止的思考方式

雖然能從 1 開始一個一個取平方直到和 num 相等為止。但是這樣太慢，能降這種線性走訪的方式就是二分搜尋了。

二分搜尋法

1. 如果正中間的平方值和 num 相等就回傳
2. 小於就改找右半邊，因為目前的值太小，需要找更大的值
3. 大於就改找左半邊，因為目前的值太大，需要找更小的值

程式碼

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        // 題目有說只會有「正數」，所以從 1 開始
        var left = 1
        var right = num

        // 二分搜尋 binary search 為基礎的變形
        while left <= right {
            let middle = left + (right - left) / 2
            let square = middle * middle

            if square == num {
                return true
            } else if square < num {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return false
    }
}

執行結果

• Runtime: 0 ms (beats 100%)
• Memory Usage: 13.5 MB (Beats 65.38%)

複雜度分析

令 n 為數字大小

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！