题目描述
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
示例 3:
输入: 9
输出: true
示例 4:
输入: 45
输出: false
进阶： 你能不使用循环或者递归来完成本题吗？
我的解法——循环（AC）
- 直接一层循环
- 时间复杂度O(logb(n) )，空间复杂度O(1)
- Beat 46%
class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
if(n == 0):
return False
while(n % 3 == 0):
n /= 3
return n == 1
最优解法——数学
- 3^i=b，则i=log3b，直接算log即可
- 陷阱：这个解决方案是有问题的，因为我们开始使用double，这意味着我们会遇到精度错误。我们不应该在比较double时使用==。这是因为Math.log10（n）/ Math.log10（3）的结果可能是5.0000001或4.9999999。通过使用函数Math.log（）而不是Math.log10（）可以观察到这种效果。 为了解决这个问题，我们需要将结果与epsilon进行比较。
public class Solution {
public boolean isPowerOfThree(int n) {
return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}
}
最优解法——能否整除
- 特别是，n是int类型的。在Java中，这意味着它是一个4字节的有符号整数[ref]。该数据类型的最大值是2147483647
- 知道了n的限制，我们现在可以推断n的三次幂的最大值是1162261467 ，计算方式如下：
- 时间复杂度：O(1)，空间复杂度O(1)
public class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
参考答案
- https://leetcode.com/problems/power-of-three/solution/