LeetCode 326. 3 的幂

2024-03-04 HGNULB 约 7 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 326. 3 的幂

题意分析

给定一个 32 位有符号整数 n，判断它是否等于 3 的某个非负整数次幂，也就是是否存在整数 $k \ge 0$ 使得 $n = 3^k$。

最容易被忽略的约束信号是输入范围：n 覆盖 $[-2^{31},\ 2^{31}-1]$，包含 0 和全部负数。而 3 的非负次幂全都是正整数，所以非正数一律为假，这个前置判断不是可选项——它同时挡住了后续除法逻辑里的死循环风险。

指数从 0 起算，意味着 $3^0 = 1$ 也算数，n = 1 必须返回 true。这一点常被误当成特例排除。

值域的上界也值得留意：int 范围内最大的 3 的幂是 $3^{19} = 1162261467$，再乘一次就会溢出。任何「从 1 开始不断乘 3 去逼近」的写法都必须处理这个溢出点。

题目还附带一个进阶要求：不使用循环或递归完成判断。这提示存在一个基于数论性质的常数时间解法。

解法：循环除法

核心思路

朴素思路有两条方向。一是从 1 开始不断乘 3，看能不能正好撞上 n；二是从 n 开始不断除以 3，看能不能正好落到 1。两者逻辑对称，但风险完全不同——乘法会在超过 $3^{19}$ 后溢出，需要额外用长整型或提前判界来兜底，而除法的中间值只会越来越小，永远不会溢出。

所以瓶颈在于「乘法方向天然带溢出隐患」，把方向反过来就消失了。

从数论角度看，$n = 3^k$ 等价于「n 的质因数分解里只含因子 3」。要验证这件事，只需要把所有的 3 反复除掉，再看剩下什么：如果一个 3 都不剩且商为 1，说明原数完全由 3 相乘构成；如果商是别的数，说明存在 3 以外的质因子。

循环维持的不变量是：设已经成功整除了 $t$ 次，则始终有「原始值 $= n \times 3^{t}$」，且当前的 n 是一个正整数。每一步除法都是精确整除，不会丢失信息，所以这个等式一直成立。

循环因为「n 不再能被 3 整除」而退出，此时原始值 $= n \times 3^{t}$ 且 n 与 3 互质。于是原始值是 3 的幂，当且仅当此时 n 恰好等于 1。判断必须放在循环结束之后——在循环内部提前下结论会漏掉指数为 0 的情况。

解题步骤

先判断 n <= 0，是则直接返回 false。这既符合「3 的非负次幂必为正」的数学事实，也挡住了 n == 0 时 0 % 3 == 0 恒成立而 0 / 3 仍为 0 造成的死循环。

只要 n % 3 == 0 就执行 n /= 3。用整除作为循环条件，保证每一步都是无损的，商乘回去能精确还原原值。

循环退出后判断 n == 1。退出意味着当前值与 3 互质：等于 1 说明原数只由若干个 3 相乘而来；大于 1 说明还残留着 3 以外的质因子，答案为假。

把判断放在循环之外而不是循环内部，这样 n = 1 这种一次除法都不执行的情况也能被正确覆盖。

以 n = 45 走一遍：45 为正，进入循环。第一轮 45 % 3 == 0，n 变成 15；第二轮 15 % 3 == 0，n 变成 5；第三轮 5 % 3 == 2 不为 0，循环退出。此时 n = 5，验证不变量：$5 \times 3^2 = 45$ 成立，而 5 显然不是 1，说明 45 除了两个 3 之外还含有质因子 5，返回 false。换成 n = 27：三轮除法依次把 n 变成 9、3、1，第四轮 1 % 3 == 1 退出，此时 $1 \times 3^3 = 27$，且 n == 1，返回 true。再换成 n = 1：循环条件 1 % 3 == 1 一次都不成立，直接跳到判断，n == 1 成立，返回 true，恰好对应 $3^0$。

代码实现

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)$，每轮循环把 n 缩小为原来的三分之一，因此循环次数不超过 $\log_3 n$；在 int 范围内这个上界是 19 次，实际是常数级。

空间复杂度：$O(1)$，全程只在原变量上做原地除法，没有递归也没有任何辅助结构。

关键点总结

「判断是否为某个底数的幂」可以统一转化为「质因数分解里是否只含该底数」，除净因子后看剩不剩 1，这个判据对 2、3、4、5 乃至任意底数都适用。

在乘法和除法两个等价方向之间，优先选让中间值变小的那个方向。除法天然免疫溢出，而乘法必须额外处理越界。

非正数要在最前面挡掉。n == 0 会让整除条件永远成立而商恒为 0，直接死循环；负数在不同语言里取模的符号规则还不一致，放进循环是纯粹的隐患。

终止判断要放在循环之外。放进循环体内提前返回，会让指数为 0（即 n = 1）这种连一次除法都不做的输入被误判。

面试视角：进阶追问几乎必然出现。因为 3 是质数，int 范围内最大的 3 的幂 $3^{19} = 1162261467$ 的所有正因数恰好就是 $3^0$ 到 $3^{19}$，所以 n > 0 && 1162261467 % n == 0 是常数时间判定。要能主动说明这一步依赖「底数是质数」，同样的技巧搬到 4 的幂上就会失效。

面试视角：如果被问到 2 的幂，要能立刻给出 n > 0 && (n & (n - 1)) == 0，同时指出这是二进制表示带来的专属捷径，3 没有对应写法。能讲清方法的前提，比会用方法更能体现水平。

易错点总结

错误写法：省略非正数判断直接进入循环。用例 n = 0 → 0 % 3 == 0 永远成立且 0 / 3 仍是 0，循环永不退出，直接超时。

错误写法：在循环体内提前下结论，写成 if (n % 3 != 0) return false;。用例 n = 1 → 第一次检查 1 % 3 = 1 就返回 false，而 $1 = 3^0$，正确答案是 true。

错误写法：额外特判 n == 1 返回 false，以为指数必须从 1 起算。用例 n = 1 → 返回 false，正确答案是 true。

错误写法：循环条件写成 while (n > 1) 并在里面无条件执行 n /= 3。用例 n = 5 → 整数除法把 5 变成 1，循环退出后判为 true，正确答案是 false。

错误写法：用浮点对数判定，Math.log(n) / Math.log(3) % 1 == 0。用例 n = 243 → 两次浮点对数相除的结果并非精确的 5，取余不为 0 而被判为 false；反向的舍入误差也可能让非幂次被误判为 true。

错误写法：改用乘法逼近但把累乘变量声明成 int。用例 n = 2147483647 → 累乘到 1162261467 后再乘 3 溢出成负数，循环条件失效，要么提前退出误判，要么陷入死循环。

错误写法：套用 2 的幂的位运算写法 n > 0 && (n & (n - 1)) == 0。用例 n = 3 → 3 & 2 等于 2 不为 0，返回 false，正确答案是 true；这个技巧只在底数为 2 时成立。

错误写法：用常数整除法但漏掉正数判断，直接写 1162261467 % n == 0。用例 n = -3 → 在 Java 中该取余结果为 0，返回 true，正确答案是 false；n = 0 时更会直接抛出除零异常。

相似题目

题目	难度	考察点
231. 2 的幂	简单	底数为 2 时可用 `n & (n - 1)` 一步判定，是二进制专属捷径
342. 4的幂	简单	先确认是 2 的幂，再要求唯一的 1 落在偶数位，多一层掩码约束
263. 丑数	简单	需要依次除净 2、3、5 三种因子，判据同样是剩余值为 1
264. 丑数 II	中等	从判定问题变成构造问题，要用多路指针按序生成第 n 个丑数