LeetCode 326. 3 的幂
题目描述
题意分析
判断整数
n是否能写成三的非负整数次幂，返回布尔值。指数允许为零，因此1也属于三的幂；零和负数不满足条件。输入范围为 32 位有符号整数。除了基本判断，题目还要求考虑不用循环或递归的做法。判断必须精确，不能只把一个数不断截断变小，或依赖浮点计算接近整数就认为它是幂。
解法：循环除法
核心思路
[!blue]
一个正整数若是三的幂，它的所有质因子都是三。不断在能够整除时将它除以三，相当于逐个去掉这些因子；若最后剩下一，说明原数没有其他因子，正好是若干个三相乘得到的。
如果某一步不能被三整除而当前值仍大于一，剩余部分就是无法去掉的其他因子，因此不是三的幂。每次除法之前必须检查余数为零，不能用整数除法的截断结果代替因子分解。
先排除非正数。尤其零对三取余为零，但除以三以后仍为零，如果直接进入循环就永远不会结束。正数每次成功相除都会严格减小，所以循环一定停止。
初始值为一时不进入循环，最终判断
n == 1自然返回真，覆盖零次幂。整个过程只做除法，不需要从一不断乘三逼近上界，因此也不会在增长过程中先发生乘法溢出。
解题步骤
n <= 0时返回假。- 只要
n % 3 == 0，就执行n /= 3。- 无法继续整除时，判断剩余值是否为一并返回。
代码实现
class Solution {
// 如果 n 是 3 的幂，反复除以 3 的过程中每一步都应该整除。
public boolean isPowerOfThree(int n) {
// 零不能参与反复整除，否则始终保持零
if (n <= 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}
func isPowerOfThree(n int) bool {
// 如果 n 是 3 的幂，反复除以 3 的过程中每一步都应该整除。
// 零不能参与反复整除，否则始终保持零
if n <= 0 {
return false
}
for n%3 == 0 {
n /= 3
}
return n == 1
}
复杂度分析
- 时间复杂度：正数输入为 $O(\log_3 n)$，每次成功除法缩小三倍；非正数直接返回。本题的 32 位范围内最多进行十九次除法。
- 空间复杂度：$O(1)$，只更新当前整数。
关键点总结
[!green]
- 精确整除是在去掉因子三，最终剩一才说明没有其他因子。
- 正数检查保证循环会缩小当前值，零次幂由最终的一自然覆盖。
- 不使用浮点对数，避免把近似相等误当成整数幂。
解法二：利用最大幂整除
核心思路
[!blue]
在 32 位有符号正整数范围内，最大的三的幂是 $3^{19} = 1162261467$，再乘三就超过上界。范围内的任意三的幂都一定能整除这个最大值。
反过来，因为三是质数，$3^{19}$ 的正因子只能是 $3^0$ 到 $3^{19}$，不可能包含其他质因子。因此，只要
n > 0且1162261467 % n == 0，就能确定n是三的幂，两个方向都成立。正数判断必须写在取余之前，利用短路求值避免
n = 0时除零。这种方法没有循环或递归，直接满足进阶要求；常数的来源是题目给定的数值范围，不能脱离这个范围使用。
解题步骤
- 判断
n是否为正数，不是则返回假。- 判断最大三的幂是否能被
n整除，返回这个结果。
代码实现
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
func isPowerOfThree(n int) bool {
return n > 0 && 1162261467%n == 0
}
复杂度分析
- 时间复杂度：$O(1)$，一次正数判断和至多一次取余。
- 空间复杂度：$O(1)$，不需要额外状态。
关键点总结
[!green]
- 质数幂的正因子仍是同一质数的幂，提供整除判定的充分性。
- 最大幂覆盖输入范围，提供整除判定的必要性。
- 先判断正数再取余，既排除无效值又避免除零。
易错点总结
[!yellow]
- 不检查能否整除就反复做整数除法，会把含有其他因子的数也截断到一。
- 漏掉非正数判断，零会进入不会变化的循环；最大幂判定中还会触发除零。
- 排除
1，会漏掉三的零次幂。- 把三的幂当成二进制单一置位，误用判断二的幂的位运算条件。
- 常数整除法依赖三是质数，以及当前输入范围内的最大三的幂；不能不加分析地推广到合数底数或更宽的整数范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 231. 2 的幂 | 简单 | 2的幂可用二进制单一置位判定，本题3的幂没有同样的位模式。 |
| 342. 4的幂 | 简单 | 同样判断固定底数的幂，但4的幂可在2的幂条件上再限制位的位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！