Medium

题目描述

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

对于一个整数 y ，如果存在整数 x 使得 y == 3^x ，我们称这个整数 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

进阶提示：

  • 请注意，在你的解法中使用的三的最大幂是 3^16
  • 如果数字的三进制表示中包含数字 2，则该数字无法表示为三的幂之和

解题思路

这道题有两种常见解法：

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

关键观察：一个数能表示为若干不同三的幂之和，当且仅当它的三进制表示中只包含 0 和 1，不包含数字 2。

原理：

  • 三进制中每一位代表对应三的幂是否被选择
  • 如果某一位是 2，意味着该位置的三的幂被使用了 2 次，违背了"不同"的要求
  • 因此只需将 n 转为三进制，检查是否包含数字 2

方法二：贪心算法

从最大的三的幂开始，依次尝试减去能减去的最大三的幂。如果最终能减到 0，则返回 true。

两种方法时间复杂度相同，但三进制转换的思路更加直观优雅，代码也更简洁。

代码实现

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
};

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

public class Solution {
    public bool CheckPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

var checkPowersOfThree = function(n) {
    while (n > 0) {
        if (n % 3 === 2) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(log₃ n)需要检查 n 的三进制表示的每一位
空间复杂度O(1)只使用常数额外空间

相关题目