LeetCode 題解 Swift 有效的完全平方數

2022-09-24 14:00:45

題目

給定一個 正整數 num，編寫一個函數，如果 num 是一個完全平方數，則返回 true，否則返回 false。

進階：不要使用任何內建的庫函數，如 sqrt。

範例 1：

輸入： num = 16

輸出： true

範例 2：

輸入： num = 14

輸出： false

方法一：使用內建的庫函數

思路及解法

根據完全平方數的性質，我們只需要直接判斷 numtextit{num}num 的平方根 xxx 是否為整數即可。對於不能判斷浮點數的值是否等於整數的語言，則可以通過以下規則判斷：

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        let x: Int = Int(sqrt(Double(num)))
        return x * x == num
    }
}

複雜度分析

程式碼中使用的 pow 函數的時空複雜度與 CPU 支援的指令集相關，這裡不深入分析。

方法二：暴力

思路及解法

程式碼

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        var x: Int = 1
        var square: Int = 1
        while square <= num {
            if square == num {
                return true
            }
            x += 1
            square = x * x
        }
        return false
    }
}

複雜度分析

方法三：二分查詢

思路及解法

細節

程式碼

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        var left: Int = 0
        var right: Int = num
        while left <= right {
            let mid = (right - left) / 2 + left
            let square = mid * mid
            if square < num {
                left = mid + 1
            } else if square > num {
                right = mid - 1
            } else {
                return true
            }
        }
        return false
    }
}