3 的幂 图解题解
这道题到底在问什么
- n
- 27
- 输出
- true
- 因为
- 27 = 3³
- 反例
- 45 → false
先想最直接的笨办法
正着乘很难枚举,倒着除反而简单:反复把 n 除以 3,只要每次都能整除(余数为 0),最终落到 1,它就是 3 的幂。（动画第 3 步）
最优解：一步一步想明白
- 3正着乘很难枚举,倒着除反而简单:反复把 n 除以 3,只要每次都能整除(余数为 0),最终落到 1,它就是 3 的幂。
- 4下面用两个例子走一遍:27(是) 和 45(不是)。盯住每一步的余数和除完的新值怎么变。
- 5当前值 = 27第一个例子 n = 27。把它放进格子里,我们要反复对它除以 3。先问:27 除以 3 余几?
- 6余数 0 → 可以除27 % 3 = 0,余数是 0,说明能被 3 整除——这一关过了,执行除法。
- 727 → 9除完!27 变成 9。旧值 27 变灰封存,指针移到新值 9,继续对 9 重复这套动作。
- 8余数 0 → 可以除对 9 再问一遍:9 % 3 = 0,还是能整除,继续。
- 99 → 39 除以 3 得 3。指针滑到新值 3,9 封存变灰。
- 10余数 0 → 可以除3 % 3 = 0,余数还是 0,最后再除一下。
- 113 → 1 · 落到 1!3 除以 3 得 1!当前值落到了 1,指针停在 1 上。
- 12落到 1 → 是 3 的幂 ✓一路整除、最终落到 1,说明 27 只由 3 相乘而来,27 是 3 的幂,返回 true。整条链 27→9→3→1 就是 3³。
- 13当前值 = 45第二个例子 n = 45。45 看着像(能被 3 除),但藏着 3 以外的因子,我们用同一套流程把它揪出来。
- 14余数 0 → 可以除45 % 3 = 0,余数 0,能整除——先别急着下结论,接着除。
- 1545 → 1545 除以 3 得 15。指针移到 15,继续盘问。
- 16余数 0 → 可以除15 % 3 = 0,还能整除,继续除。
- 1715 → 515 除以 3 得 5。指针移到 5——5 既不是 1,也明显不像 3 的倍数,关键一步来了。
- 18余数 2 → 出局5 % 3 = 2,余数不是 0!这说明 45 里藏着 5 这个 3 以外的因子,除不动了。
- 19卡在 5 → 不是 3 的幂 ✗流程停在 5,没能落到 1,说明 45 不是 3 的幂,返回 false。45 = 3² × 5,那个 5 让它出局。
- 20当前值 = 81再来一例 81 = 3⁴,它要连除 4 次才到 1,正好看清楚 while 循环「除到底」是什么意思。
- 2181 → 2781 % 3 = 0,除一次得 27,指针前移、81 封存。
- 2227 → 927 也整除,得 9,继续往下除。
- 239 → 39 整除得 3,只差最后一步。
- 243 → 1 · 落到 1!第 4 次除得 1!整条链 81→27→9→3→1 每步余数全 0、干净落到 1,所以 81 是 3 的幂。是 3 的幂的数,这条链一定能走到底。
- 25整个算法就是一个 while 循环:只要还能被 3 整除就除,循环停下后,看当前值是不是正好等于 1。
- 290 % 3 = 0 却永远到不了 1假如不写 if n < 1:n=0 时 0%3 也等于 0,除完还是 0,永远落不到 1(还可能死循环)。这就是为什么开头要先挡掉 0 和负数。
⚠️ 容易写错的地方
✗ 错：忘了挡 n ≤ 0
✓ 对：开头先 if n < 1 return False
n=0 会让 0%3==0 成立但永远到不了 1;负数同理,必须先排除
✗ 错：用 if 只除一次
✓ 对：用 while 一直除到不能整除
如 27 要连除 3 次才到 1,只除一次会误判
✗ 错：误以为「能被 3 整除」就是 3 的幂
✓ 对：必须除到底看是否等于 1
45 能被 3 整除,但除到 5 卡住,并不是 3 的幂
完整代码（Python / C++ / Java）
Python
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1: # 0 和负数直接出局
return False
while n % 3 == 0: # 能整除就一直除
n //= 3
return n == 1 # 最终落到 1 才是 3 的幂C++
class Solution {
public:
bool isPowerOfThree(int n) {
if (n < 1) return false; // 0 和负数出局
while (n % 3 == 0) { // 能整除就一直除
n /= 3;
}
return n == 1; // 落到 1 才是
}
};Java
class Solution {
public boolean isPowerOfThree(int n) {
if (n < 1) return false; // 0 和负数出局
while (n % 3 == 0) { // 能整除就一直除
n /= 3;
}
return n == 1; // 落到 1 才是
}
}复杂度
时间复杂度
O(log₃ n)
每次把 n 缩小为原来的 1/3,最多除 log₃n 次就到 1 或卡住
空间复杂度
O(1)
只用了 n 本身一个变量,没有额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 3 的幂 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用循环、O(1) 判断?+
可以。int 范围内最大的 3 的幂是 3¹⁹ = 1162261467,它的因子只有 3。所以 n>0 且 1162261467 % n == 0 即可,一行搞定。
为什么 1162261467 % n == 0 就够了?+
3¹⁹ 的所有因子都是 3 的幂(3⁰~3¹⁹)。若 n 能整除 3¹⁹,n 必然也是 3 的幂;反之含别的因子就除不尽。
时间复杂度对比?+
循环法 O(log₃n);取模法 O(1)。两者都很快,面试讲清楚取模法的数学依据是加分点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 3 的幂 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。