共计 1886 个字符，预计需要花费 5 分钟才能阅读完成。

题目描述：

给你一个整数  n ，如果你可以将  n  表示成若干个不同的三的幂之和，请你返回  true ，否则请返回  false 。

对于一个整数  y ，如果存在整数  x  满足  y == 3x ，我们称这个整数  y  是三的幂

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

我的分析

读懂了题目以后，我第一反应还是枚举，我想，用目标数 n，从小于等于 n 的最大的一个 3 的幂开始枚举

用 n 减去它们，逐步相减，最终如果能够剩余为 0，那么符合题目要求返回 true

一开始我的想法是：类似以上想法，但最终相减到最后如果 剩余的数小于下一个 3 的幂，可能就无法凑成目标数 n，但我有疑问，难道 在往后面的三的幂就不能凑成当前的剩余数了吗？

但我又想不到方法佐。

但豆包给我提示：它发现了规律：所有三的幂 都 >= 小于它的所有三的幂的和

那么有结论:

所以如果 n 能被表示成不同三的幂之和，必须包含不超过 n 的最大那个三的幂。否则，剩下的小幂加起来都不够凑出 n。

比如 n=12，最大的三的幂是 9（3²），12-9=3，剩下的 3 正好是 3¹，所以可行。

于是得到一个思路：

1. 生成所有≤n 的三的幂（3⁰, 3¹, 3²…），按从大到小排序；
2. 用 n 依次减去这些幂（每个幂最多减一次）；（题目条件，要求不同的三的幂）
3. 最后如果剩下的数是 0，返回 true，否则 false。

那么我们就可以用代码实现了，首先实现前两一步

const  checkPowersOfThree = (n)=>{
 let i = 0;
    let num = 0;
    let arr = []
    let remainder = n
    let res;  // 前面初始化一些变量
// 记录
    while (1) {num = Math.pow(3, i)
        if (num > n) {break;   // 终止条件}
        arr.push(num)
        i++;
    }
    arr.sort((a, b) => b - a) // 从大到小排序

我们已经得到了一个数组 arr, 它保存着 所有符合条件的候选的三的幂，并且从大到小排序

接下来解决最后的步骤 相减 并判断条件

  for (let item of arr) {if (remainder >= item) {remainder = remainder - item}
    }
    res = remainder === 0 ? true : false

    // 每次迭代的数  那么 num 就是当前迭代的候选数
    // n  num  --  

    // dp[j] = dp[j] + dp[j-num]
    // 倒叙 n - num  
    // num 下一个幂 n，num n  n -- ---  < 3^x   ==>  凑不成 27 / 51  2<3  ==> 

    //
    return res
};

最终返回布尔值 即可。

方法总结：

与上面的思路相似。

通过这个方法，我也得到一个数学性质，与上面提到的类似：所有三的幂 都 >= 小于它的所有三的幂的和

这个题目的核心还是数学性质。

方法二，进制转换

我们可以将 n 转换成 3 进制。如果 n 的 3 进制表示中每一位均不为 2，那么答案为 True，否则为 False。

例如当 n=12 时，12=(110) 满足要求；当 n=21 时，21=(210) 不满足要求。

解释：三进制的每一位系数直接对应“该位三的幂的使用次数”。

先回忆三进制的含义

任何整数都可以用三进制表示，形式为：n=ak​⋅3k+ak−1​⋅3k−1+…+a1​⋅31+a0​⋅30

三进制的每一位数字，本质上代表了对应“三的幂”的使用次数。

为什么会想到进制转换的方法？

题目要求 n 必须是“若干个 不同 的三的幂之和”。用数学式子写出来就是：

其中，每个系数 \(a_i\)只能是0 或 1（因为“不同”意味着每个三的幂最多用 1 次：用了就是 1，不用就是 0）。

然而，三进制的表示天然包含“三的幂的组合”

我们知道，任何整数的三进制表示都可以写成：

其中，每个系数 \(b_i\)的取值范围是0、1、2（这是三进制的定义：基数为 3，每一位最大为基数 – 1）。

这种思路的产生，本质上是注意到了“问题中的和式结构”与“进制表示的和式结构”完全一致 —— 都是“基数的幂乘以系数的累加”。

当基数固定为 3 时，问题的限制（系数只能是 0 或 1）就转化为对三进制系数的限制（不能出现 2）。这种“结构上的同构性”使得进制转换成为了最直接、最简洁的解法。

于是，最终代码实现：

var checkPowersOfThree = function(n) {while (n !== 0) {if (n % 3 === 2) {return false;}
        n = Math.floor(n / 3);
    }
    return true;
};

反思

这里是展开了题目的要求，由此想到了进制转换的展开式，其实很多关于数的题目也能用到进制转换，属于是经验性质的，但是如果用分析的方法 也能想到用进制转换~