LeetCode 1780：判断一个数字是否可以表示成3的幂的和-进制转换解法-EW帮帮网

LeetCode 1780：判断一个数字是否可以表示成3的幂的和 - 算法详解与优化

题目描述

给定一个整数 n，判断该整数是否可以表示成若干个不同的3的幂次方的和。

示例：

输入：n = 12
输出：true
解释：12 = 3¹ + 3²
输入：n = 91
输出：true
解释：91 = 3⁰ + 3² + 3⁴
输入：n = 21
输出：false

问题分析

这个问题本质上是在问：给定一个数字n，是否存在一组不同的3的幂次方，使得它们的和等于n。

关键观察

3的幂次方的特点：3⁰=1, 3¹=3, 3²=9, 3³=27, 3⁴=81, …
不同幂次方的和：每个3的幂次方最多只能使用一次
进制转换思想：这个问题可以转化为三进制表示问题

算法思路

方法一：进制转换法（推荐）

将数字n转换为三进制，如果三进制表示中只包含0和1，则返回true；如果包含2，则返回false。

原理：

如果一个数字可以表示成3的幂的和，那么在三进制中，每一位只能是0或1
如果某一位是2，说明需要两个相同的3的幂次方，这与"不同的3的幂次方"矛盾

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n > 0:
            if n % 3 == 2:
                return False
            n //= 3
        return True

方法二：迭代判断法

通过不断除以3，检查每一步的余数：

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        for _ in range(20):  # 设置合理的循环次数
            if n % 3 == 2:
                return False
            n //= 3
            if n == 0:
                break
        return True

算法复杂度分析

时间复杂度：O(log₃ n)，因为每次除以3，数字会减少到原来的1/3
空间复杂度：O(1)，只使用了常数个变量

详细代码实现

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        """
        判断一个数字是否可以表示成3的幂的和
        
        思路：将数字转换为三进制，如果三进制表示中只包含0和1，则返回True
        如果包含2，则返回False
        
        Args:
            n: 待判断的整数
            
        Returns:
            bool: 是否可以表示成3的幂的和
        """
        while n > 0:
            # 检查当前位的余数
            if n % 3 == 2:
                return False
            # 继续处理下一位
            n //= 3
        return True

# 测试代码
if __name__ == '__main__':
    solution = Solution()
    
    # 测试用例
    test_cases = [12, 91, 21, 1, 3, 9, 27, 81]
    
    for num in test_cases:
        result = solution.checkPowersOfThree(num)
        print(f"数字 {num} 是否可以表示成3的幂的和: {result}")

算法正确性证明

充分性证明

如果一个数字的三进制表示只包含0和1，那么它一定可以表示成3的幂的和。

证明：

三进制中的每一位对应一个3的幂次方
如果某一位是1，说明使用了对应的3的幂次方
如果某一位是0，说明没有使用对应的3的幂次方
因此，整个数字就是所有为1的位对应的3的幂次方的和

必要性证明

如果一个数字可以表示成3的幂的和，那么它的三进制表示一定只包含0和1。

证明：

假设存在一个数字，它的三进制表示包含2
这意味着需要两个相同的3的幂次方
但这与"不同的3的幂次方"矛盾
因此，三进制表示不能包含2

扩展思考

1. 其他进制的情况

这个问题可以推广到其他进制。例如：

判断一个数字是否可以表示成2的幂的和（二进制问题）
判断一个数字是否可以表示成4的幂的和（四进制问题）

2. 动态规划解法

虽然对于这个问题，进制转换法是最优解，但也可以考虑动态规划：

def checkPowersOfThree_dp(n: int) -> bool:
    """
    动态规划解法（仅作参考，实际效率较低）
    """
    if n <= 0:
        return False
    
    # 生成所有可能的3的幂次方
    powers = []
    power = 1
    while power <= n:
        powers.append(power)
        power *= 3
    
    # 使用集合记录可达的数字
    reachable = {0}
    
    for p in powers:
        new_reachable = set()
        for num in reachable:
            if num + p <= n:
                new_reachable.add(num + p)
        reachable.update(new_reachable)
    
    return n in reachable

实际应用场景

数字编码：在某些编码系统中，需要将数字表示为特定幂次方的和
数据压缩：利用幂次方的特性进行数据压缩
数学研究：在数论研究中，幂次方的表示是一个重要问题

总结

LeetCode 1780这道题目通过进制转换的思想，巧妙地解决了判断一个数字是否可以表示成3的幂的和的问题。核心思路是：

问题转化：将原问题转化为三进制表示问题
关键观察：三进制表示中不能包含2
算法实现：通过不断除以3并检查余数来判断

这道题目不仅考察了算法思维，也体现了数学思维在算法设计中的重要作用。掌握这种进制转换的思想，对于解决类似问题具有重要的启发意义。

关键词：LeetCode、算法、进制转换、3的幂、数学思维、Python

LeetCode 1780：判断一个数字是否可以表示成3的幂的和-进制转换解法