标签: 数学
难度: Medium
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12 输出：true 解释：12 = 31 + 32
示例 2：
输入：n = 91 输出：true 解释：91 = 30 + 32 + 34
示例 3：
输入：n = 21 输出：false
提示：
1 <= n <= 107运行时间: 26 ms
内存: 16.0 MB
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
pre = [3**i for i in range(15)]
for i in range(len(pre) - 1, -1, -1):
if pre[i] <= n:
n -= pre[i]
return n == 0
此题解使用了贪心算法的思想。首先，生成了一个列表pre，其中包含了从3^0到3^14的所有三的幂。这是基于题目给定的最大n值10^7，3^14是不超过10^7的最大三的幂。接着，算法从最大的三的幂开始，尝试从n中减去这些三的幂，如果当前的三的幂小于或等于n，那么从n中减去该三的幂，并继续尝试下一个较小的三的幂。这个过程从最大的三的幂开始，直到3^0。最终，如果n减到0，说明n可以完全由不同的三的幂组成，返回true；否则，返回false。
时间复杂度: O(1)
空间复杂度: O(1)
# 定义解决方案类
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
# 计算并存储所有可能需要的3的幂
pre = [3**i for i in range(15)]
# 从最大的3的幂开始尝试
for i in range(len(pre) - 1, -1, -1):
# 如果当前3的幂小于等于n，则从n中减去这个幂
if pre[i] <= n:
n -= pre[i]
# 如果n减至0，则可以表示为不同的3的幂之和
return n == 0
通过计算可知，3^14等于4782969，这是小于10^7的最大的三的幂。考虑到题目给出的n的最大值是10^7，使用3^14足以覆盖所有可能的n，因为任何大于3^14的三的幂都将超过10^7，不会是有效的候选。同时，如果使用小于3^14的最大幂，我们可能无法覆盖所有小于10^7的n值。
在此算法中，每个三的幂只能使用一次。算法从最大的三的幂开始，逐一尝试是否可以从n中减去这个三的幂。由于每个三的幂只考虑一次，即便较小的三的幂可以被多次减去，也不会影响结果，因为我们的目标是检查能否仅通过不同的三的幂的和来表示n。
算法确实考虑了所有三的幂只能使用一次的规则。通过从最大到最小的顺序尝试每个三的幂，并且每个幂只在决定可以减去后使用一次，保证了每个幂的独立使用。如果存在重复使用的情况，则可能需要重新检查算法逻辑，确保每个幂在循环中只被尝试一次。
基于贪心算法的此解法，从最大的幂开始尝试，可以有效地覆盖所有可能的组合。因为如果存在一种正确的组合方式，那么从大到小使用三的幂是符合逻辑的，这样可以最快地减少n的值。理论上，此方法不会错过任何可行的组合，因为它确保了在任何时候都尽可能使用最大可用的幂，从而达到最优解。