3 的幂
难度:
标签:
题目描述
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3x.
Example 1:
Input: n = 27 Output: true Explanation: 27 = 33
Example 2:
Input: n = 0 Output: false Explanation: There is no x where 3x = 0.
Example 3:
Input: n = -1 Output: false Explanation: There is no x where 3x = (-1).
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
代码结果
运行时间: 40 ms, 内存: 16.1 MB
/*
* 思路：
* 我们可以使用Stream和数学方法来解决这个问题。
* 计算最大的3的幂次方，然后判断给定的n是否能整除该幂次方。
* 我们使用Math.log来计算log3(n)，然后判断其是否为整数。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) return false;
int maxPowerOfThree = (int) Math.pow(3, (int)(Math.log(Integer.MAX_VALUE) / Math.log(3)));
return n > 0 && maxPowerOfThree % n == 0;
}
}解释
方法:
这个题解的思路是首先检查输入的整数是否为0或者偶数，如果是，则直接返回False，因为0和偶数都不可能是3的幂次方。接着，使用一个循环不断地将n除以3，直到n不能被3整除。最后，如果n变为1，那么说明原始的n是3的幂次方，返回True；否则，返回False。
时间复杂度:
O(log3(n))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在题解中首先检查输入整数n是否为偶数？3的幂次方与偶数之间有什么关系？
▷🦆
题解中提到如果n是0或偶数就返回False，但是为什么0特殊情况的处理与偶数可以一起处理？0和偶数是否有本质的区别在这个问题中？
▷🦆
在题解中使用了循环来不断地将n除以3直到不能整除，这种方法在n是非常大的负数时会有什么表现？
▷