1780.判断一个数字是否可以表示成三的幂的和
【LetMeFly】1780.判断一个数字是否可以表示成三的幂的和
力扣题目链接: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 = 31 + 32
示例 2:
输入:n = 91 输出:true 解释:91 = 30 + 32 + 34
示例 3:
输入:n = 21 输出:false
提示:
1 <= n <= 107
也可直接看效率更高的方法二
方法一:二进制枚举
题目分析
因此,想要数个不同的
每个数有“选”与“不选”两种选择,因此最多有
解题思路
那么,我们直接开辟一个数组,把所有的小于等于
1 |
|
接下来,用一个整数
每个
1 |
|
复杂度分析
- 时间复杂度
- 空间复杂度
AC代码
C++
1 |
|
方法二:进制转换
我们只需要将
例如
- 时间复杂度
- 空间复杂度
AC代码
C++
1 |
|
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/128248159
1780.判断一个数字是否可以表示成三的幂的和
https://blog.letmefly.xyz/2022/12/09/LeetCode 1780.判断一个数字是否可以表示成三的幂的和/