题目
给定一个整数，写一个函数来判断它是否是 的幂次方。如果是，返回
；否则，返回
。
整数 是
的幂次方需满足：存在整数
使得
示例 1：
- 输入：
n = 27- 输出：
true
示例 2：
- 输入：
n = 0- 输出：
false
示例 3：
- 输入：
n = 9- 输出：
true
示例 4：
- 输入：
n = 45- 输出：
false
提示：
方法一：试除法
思路及解法
我们不断地将 除以
，直到
。如果此过程中
无法被
整除，就说明
不是
的幂。
本题中的 可以为负数或
，可以直接提前判断该情况并返回
，也可以进行试除，因为负数或
也无法通过多次除以
得到
。
代码
class Solution {
func isPowerOfThree(_ n: Int) -> Bool {
if n <= 0 {
return false
}
var n = n
while n % 3 == 0 {
n /= 3
}
return n == 1
}
}
复杂度分析
时间复杂度：
。当
是
的幂时，需要除以
；当
空间复杂度：
。
方法二：判断是否为最大 3 的幂的约数
思路及解法
我们还可以使用一种较为取巧的做法。
题目要求不能使用循环或递归来做，而传参 的数据类型为
，这引导我们首先分析出
范围内的最大
次幂是多少，约为
。
如果 为
的幂的话，那么必然满足
，即
与
存在倍数关系。
因此，我们只需要判断 是否为
的约数即可。
与方法一不同的是，这里需要特殊判断 是负数或
的情况。
注意：这并不是快速判断
的幂的通用做法，当且仅当
代码
class Solution {
func isPowerOfThree(_ n: Int) -> Bool {
return n > 0 && 1162261467 % n == 0
}
}
复杂度分析
时间复杂度：
空间复杂度：
