題目
給定一個(gè)整數(shù)，寫一個(gè)函數(shù)來判斷它是否是 的冪次方咏尝。如果是格侯，返回
；否則押袍，返回
。
整數(shù) 是
的冪次方需滿足：存在整數(shù)
使得
示例 1：
- 輸入：
n = 27- 輸出：
true
示例 2：
- 輸入：
n = 0- 輸出：
false
示例 3：
- 輸入：
n = 9- 輸出：
true
示例 4：
- 輸入：
n = 45- 輸出：
false
提示：
方法一：試除法
思路及解法
我們不斷地將 除以
凯肋，直到
谊惭。如果此過程中
無法被
整除，就說明
不是
的冪侮东。
本題中的 可以為負(fù)數(shù)或
圈盔，可以直接提前判斷該情況并返回
，也可以進(jìn)行試除苗桂，因?yàn)樨?fù)數(shù)或
也無法通過多次除以
得到
药磺。
代碼
class Solution {
func isPowerOfThree(_ n: Int) -> Bool {
if n <= 0 {
return false
}
var n = n
while n % 3 == 0 {
n /= 3
}
return n == 1
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
。當(dāng)
是
的冪時(shí)煤伟，需要除以
癌佩；當(dāng)
空間復(fù)雜度：
围辙。
方法二：判斷是否為最大 3 的冪的約數(shù)
思路及解法
我們還可以使用一種較為取巧的做法。
題目要求不能使用循環(huán)或遞歸來做放案，而傳參 的數(shù)據(jù)類型為
姚建，這引導(dǎo)我們首先分析出
范圍內(nèi)的最大
次冪是多少，約為
吱殉。
如果 為
的冪的話掸冤，那么必然滿足
，即
與
存在倍數(shù)關(guān)系友雳。
因此稿湿，我們只需要判斷 是否為
的約數(shù)即可。
與方法一不同的是押赊，這里需要特殊判斷 是負(fù)數(shù)或
的情況饺藤。
注意：這并不是快速判斷
的冪的通用做法，當(dāng)且僅當(dāng)
代碼
class Solution {
func isPowerOfThree(_ n: Int) -> Bool {
return n > 0 && 1162261467 % n == 0
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
空間復(fù)雜度：
