326.3 的幂
标签: math
难度: Easy
通过率: 47.36%
原题链接: https://leetcode.com/problems/power-of-three/description/
题目描述
给定一个整数 ,如果它是 的幂,则返回 true
;否则,返回 false
。如果存在一个整数 使得 ,则整数 是 3 的幂。
解题思路
要判断一个数是否是3的幂,可以使用循环或递归的方法,对数字进行反复除以3直到不能被3整除,如果最终结果为1则说明这个数是3的幂。具体步骤如下:
1. 如果 $n <= 0$,那么它不可能是3的幂,直接返回 false。
2. 循环判断,若 $n$ 能被3整除,则不断除以3;否则跳出循环。
3. 最后检查,如果结果是1,则 $n$ 是3的幂,返回 true;否则返回 false。
在不使用循环/递归的情况下,我们可以利用3的幂的性质:
- 在整数范围内最大的3的幂是 (即 )。我们可以检查 是否是 的约数,如果是,则 是3的幂。
这种方法的实现如下:
- 检查 且 。
代码实现
- Python
- C++
- JavaScript
- Java
def isPowerOfThree(n: int) -> bool:
# 用循环的方法判断是否为3的幂
# 如果 n 小于等于0,直接返回 False
if n <= 0:
return False
# 当 n 能整除 3 时,不断将 n 除以 3
while n % 3 == 0:
n //= 3
# 若 n 最后变成1,说明它是3的幂
return n == 1
class Solution {
public:
bool isPowerOfThree(int n) {
// 用循环的方法判断是否为3的幂
if (n <= 0) return false;
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
};
function isPowerOfThree(n) {
// 用循环的方法判断是否为3的幂
if (n <= 0) return false;
while (n % 3 === 0) {
n /= 3;
}
return n === 1;
}
public class Solution {
public boolean isPowerOfThree(int n) {
// 不用循环的方法 - 最大的 int 范围内 3 的幂是 1162261467 (3^19)
return (n > 0 && 1162261467 % n == 0);
}
}
复杂度分析
时间复杂度:对于循环方法,最坏情况下需要不断除以3,时间复杂度为 。对于不使用循环/递归的方法,则为 。
空间复杂度:,不需要额外的空间。