0326. Power of Three¶
题目信息¶
- 题号:
0326
- 难度:
Easy
- 主题:
整数、幂、指数、正数边界
- 原题:
- 重点:
指数必须是整数、
3^0等于 1、零和负数都不是三的幂
题目重述¶
给定 32 位有符号整数 n,判断是否存在整数 x 使 n = 3^x。由于结果需要是整数且三的整数次幂为正数,只有正整数可能满足条件。
n 位于 [-2^31, 2^31-1]。指数 x 可以为 0,所以 1 = 3^0 应返回 true;0、负数以及含有其他质因子的正整数都应返回 false。进阶问题询问能否不使用循环或递归完成判断。
自建示例¶
较高次幂:
输入:n = 81
输出:true
解释:81 = 3^4,因此存在整数指数满足条件。
零不是三的幂:
输入:n = 0
输出:false
解释:任意整数指数下的 3 的幂都不会等于 0。
指数为零:
输入:n = 1
输出:true
解释:1 = 3^0。
反复除以 3 验证质因子¶
正数 n 若是 3 的幂,连续除以 3 后一定恰好得到 1;过程中只要出现不能整除 3 的余数,就说明还含有其他质因子,不能再成为三的幂。先排除非正数,n == 1 会自然地在循环前通过。
这里不使用对数判断,因为浮点对数在整数幂附近可能有舍入误差;除法循环直接操作整数,也清楚地覆盖 3^0 的边界。
C++ 实现¶
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) return false;
while (n % 3 == 0) n /= 3;
return n == 1;
}
};
代码分析¶
每次循环都去掉一个 3 因子;如果原数是 3^x,最终只剩 1,如果不是,剩余数会大于 1。循环次数为 O(log_3 n),额外空间为 O(1)。这没有采用题目进阶中“不使用循环”的常数技巧,但避免了把一个未解释的最大幂常量当作结论。