1780. 判定一个数字是否可以表现成三的幂的和（难度：中等）

手机游戏开发者 · 2024-9-7 18:02:28

标题链接：https://leetcode.cn/problems/check-if-number-is-a-sum-of-powers-of-three/

标题形貌：

给你一个整数 n ，如果你可以将 n 表现成多少个差异的三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满意 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12输出：true解释：12 = 3^1 + 3^2示例 2：
输入：n = 91输出：true解释：91 = 3^0 + 3^2 + 3^4示例 3：
输入：n = 21输出：false提示：

1 <= n <= 10^7

解法：贪婪+递归

根据标题意思，我们可以通过递归的头脑，不停的减小n，直到其小于3，可以很快的判定是否满意标题意思。
使用贪婪思绪，每次找到不大于 n 的最大3的幂temp，让n减去temp再举行下一轮递归。
边界条件：

若 n >= 2 * temp，即下一轮递归，找到不大于 n 的最大3的幂还是temp，不满意标题条件。
若 n < 3 时，如果 n == 0 大概 n == 1，则满意条件。

1780. 判定一个数字是否可以表现成三的幂的和（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品