当前位置：首页 > news >正文

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

news 2025/8/15 5:51:51

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 Falsen //= 3return True

方法二：迭代判断法

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

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

算法复杂度分析

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

详细代码实现

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