江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第326题：3的幂

给定一个整数 n，判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

📖 文章摘要

本文详细解析LeetCode第326题“3的幂”，这是一道数学问题。文章提供了循环、递归和数学方法三种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学思维能力的程序员。

核心知识点： 数学、递归、整数性质
难度等级： 简单
推荐人群： 初学者，想要提升数学思维能力的程序员

题目描述

给定一个整数 n，判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例

示例 1：

输入：n = 27
输出：true
解释：27 = 3^3

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true
解释：9 = 3^2

提示

  • -2^31 <= n <= 2^31 - 1
  • 进阶：你能不使用循环或者递归来完成本题吗？

解题思路

方法一：循环除法

通过不断除以3来判断是否为3的幂。

关键点：

  • 处理边界情况（0和负数）
  • 循环除以3直到不能整除
  • 判断最后的结果是否为1

具体步骤：

  1. 处理特殊情况（n <= 0）
  2. 循环除以3直到不能整除
  3. 判断最终结果是否为1

时间复杂度：O(log n) 空间复杂度：O(1)

方法二：递归法

使用递归的方式判断是否为3的幂。

关键点：

  • 基线条件的判断
  • 递归调用时除以3
  • 处理边界情况

具体步骤：

  1. 处理特殊情况
  2. 如果n为1，返回true
  3. 如果n不能被3整除，返回false
  4. 递归调用n/3

时间复杂度：O(log n) 空间复杂度：O(log n)

方法三：数学方法

利用整数的性质来判断。

关键点：

  • 在32位整数范围内，3的最大幂是3^19 = 1162261467
  • 如果n是3的幂，那么1162261467除以n的余数一定是0

具体步骤：

  1. 处理特殊情况
  2. 判断1162261467是否能被n整除

时间复杂度：O(1) 空间复杂度：O(1)

图解思路

循环除法过程分析表

输入值 除以3后 是否能整除 结果
27 9 是 继续
9 3 是 继续
3 1 是 返回true

数学方法原理表

3的幂次 值 是否在范围内
3^0 1 是
3^1 3 是
3^2 9 是
… … …
3^19 1162261467 是
3^20 3486784401 超出范围

代码实现

C# 实现

public class Solution {
    // 方法一：循环除法
    public bool IsPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
    
    // 方法二：递归法
    public bool IsPowerOfThreeRecursive(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        if (n % 3 != 0) return false;
        return IsPowerOfThreeRecursive(n / 3);
    }
    
    // 方法三：数学方法
    public bool IsPowerOfThreeMath(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

Python 实现

class Solution:
    # 方法一：循环除法
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1
    
    # 方法二：递归法
    def isPowerOfThreeRecursive(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        if n % 3 != 0:
            return False
        return self.isPowerOfThreeRecursive(n // 3)
    
    # 方法三：数学方法
    def isPowerOfThreeMath(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

C++ 实现

class Solution {
public:
    // 方法一：循环除法
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
    
    // 方法二：递归法
    bool isPowerOfThreeRecursive(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        if (n % 3 != 0) return false;
        return isPowerOfThreeRecursive(n / 3);
    }
    
    // 方法三：数学方法
    bool isPowerOfThreeMath(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

执行结果

C# 实现

  • 执行用时：52 ms
  • 内存消耗：28.4 MB

Python 实现

  • 执行用时：68 ms
  • 内存消耗：15.7 MB

C++ 实现

  • 执行用时：8 ms
  • 内存消耗：5.9 MB

性能对比

语言 执行用时 内存消耗 特点
C# 52 ms 28.4 MB 实现简洁，性能适中
Python 68 ms 15.7 MB 代码最简洁
C++ 8 ms 5.9 MB 性能最优

代码亮点

  1. 🎯 提供了三种不同的解法思路
  2. 💡 数学方法的巧妙运用
  3. 🔍 边界情况的完整处理
  4. 🎨 代码结构清晰，易于理解

常见错误分析

  1. 🚫 没有处理负数和0的情况
  2. 🚫 整数溢出问题
  3. 🚫 递归深度过大
  4. 🚫 除法精度问题

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
循环除法 O(log n) O(1) 直观易懂 性能一般
递归法 O(log n) O(log n) 代码简洁 空间消耗大
数学方法 O(1) O(1) 性能最优 不够直观

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第326题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！