LeetCode 326 3的幂

判断一个数是否是 3 的幂次方：Java 实现与算法分析

一、问题描述

给定一个整数 n，编写一个函数判断它是否是 3 的幂次方。
满足条件：存在整数 x 使得 n == 3^x。
示例：

• 输入：27 → 输出：true（3³=27）
• 输入：0 → 输出：false（3 的任何次幂都不为 0）
• 输入：-3 → 输出：false（幂次方结果为正整数）

二、解决方案

方法一：循环迭代法（通用思路）

核心思想

不断将数字除以 3，直到无法整除为止。若最终结果为 1，则是 3 的幂；否则不是。
步骤：

1. 处理边界条件：n ≤ 0 直接返回 false（3 的幂必为正整数）。
2. 循环除以 3，直到余数不为 0。
3. 检查最终结果是否为 1。

代码实现

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) { // 处理负数和0
            return false;
        }
        while (n % 3 == 0) { // 能被3整除时继续除
            n /= 3;
        }
        return n == 1; // 最终结果是否为1
    }
}

复杂度分析

• 时间复杂度：O (log₃n)，循环次数等于 3 的幂次（如 3¹⁹需要循环 19 次）。
• 空间复杂度：O (1)，仅使用常数额外空间。

优缺点

• 优点：通用，适用于判断任意数的幂（如 2 的幂、5 的幂）。
• 缺点：大数时循环次数较多（如 3¹⁹需要 19 次循环）。

方法二：数学性质法（Java 特化优化）

核心思想

利用 Java 中int类型的范围限制：

• int最大值为 2¹⁴⁷⁴⁸³⁶⁴⁷，3 的最大幂次方为 3¹⁹ = 1,162,261,467（3²⁰超过 int 范围）。
• 若n是 3 的幂，则1,162,261,467必能被n整除（因为 3¹⁹是 3 的所有幂的倍数）。

代码实现

class Solution {
    public static final int MAX_POWER_OF_3 = 1162261467; // 3¹⁹
    
    public boolean isPowerOfThree(int n) {
        return n > 0 && MAX_POWER_OF_3 % n == 0;
    }
}

关键细节

• 边界条件：n > 0 排除负数和 0。
• 数学原理：3¹⁹是 3 的所有幂的倍数（如 3⁰=1，3¹=3，…，3¹⁹）。若n是 3 的幂，则必为 3¹⁹的因数。

复杂度分析

• 时间复杂度：O (1)，仅一次取模运算。
• 空间复杂度：O (1)，常数空间。

优缺点

• 优点：极致优化，常数时间复杂度。
• 缺点：依赖编程语言的整数范围（如 Java 的int），移植性较差。

三、两种方法对比

四、测试用例

五、扩展思考

1. 如何判断 2 的幂？
   • 循环法：同上。
   • 数学法：利用位运算（n & (n-1) == 0），更高效。
2. 大数处理：若n超过int范围（如long），数学法需调整最大幂值。
3. 质因数分解：3 的幂的质因数只能是 3。若n的质因数包含其他数（如 5），则不是 3 的幂。

六、总结

• 循环迭代法：通用、易理解，适合教学和通用场景。
• 数学性质法：Java 特化优化，极致性能，适合已知整数范围的场景。
• 选择建议：根据语言特性和场景选择。若需跨语言或通用逻辑，选循环法；若追求极致性能（Java），选数学法。

七、完整代码（含测试）

class Solution {
    // 方法一：循环迭代法
    public boolean isPowerOfThreeLoop(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }

    // 方法二：数学性质法
    private static final int MAX_POWER = 1162261467;
    public boolean isPowerOfThreeMath(int n) {
        return n > 0 && MAX_POWER % n == 0;
    }

    // 测试示例
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] testCases = {0, 1, 3, 9, 27, 45, -3, 1162261467};
        for (int n : testCases) {
            boolean loopResult = solution.isPowerOfThreeLoop(n);
            boolean mathResult = solution.isPowerOfThreeMath(n);
            System.out.printf("n=%-10d 循环法：%-5b 数学法：%-5b%n", 
                            n, loopResult, mathResult);
        }
    }
}

输出结果：

n=0          循环法：false  数学法：false  
n=1          循环法：true   数学法：true   
n=3          循环法：true   数学法：true   
n=9          循环法：true   数学法：true   
n=27         循环法：true   数学法：true   
n=45         循环法：false  数学法：false  
n=-3         循环法：false  数学法：false  
n=1162261467 循环法：true   数学法：true