C++ LeetCode1780判断数字是否可以表示成三的幂的和
目录
- LeetCode 1780.判断一个数字是否可以表示成三的幂的和
- 方法一:二进制枚举
- 题目分析
- 解题思路
- 复杂度分析
- AC代码
- C++
- 方法二:进制转换
- AC代码
- C++
LeetCode 1780.判断一个数字是否可以表示成三的幂的和
力扣题目链接:leetcode.cn/problems/ch…
给你一个整数 n
,如果你可以将 n
表示成若干个不同的三的幂之和,请你返回 true
,否则请返回 false
。
对于一个整数 y
,如果存在整数 x
满足 y == 3x
,我们称这个整数 y
是三的幂。
方法一:二进制枚举
题目分析
解题思路
那么,我们直接开辟一个数组,把所有的小于等于nnn的“3的幂”放入数组
vector<int> three(1, 1); // 初始值是1个1 while (three.back() < n) { three.push_back(three.back() * 3); }
int num = three.size(), to = 1 << num; for (int state = 0; state < to; state++) { int s = 0; for (int j = 0; j < num; j++) { if (state & (1 << j)) { s += three[j]; } } if (s == n) return true; } return false;
复杂度分析
AC代码
C++
class Solution { public: bool checkPowersOfThree(int n) { vector<int> three(1, 1); while (three.back() < n) { three.push_back(three.back() * 3); } int num = three.size(), to = 1 << num; for (int state = 0; state < to; state++) { int s = 0; for (int j = 0; j < num; j++) { if (state & (1 << j)) { s += three[j]; } } if (s == n) return true; } return false; } };
方法二:进制转换
AC代码
C++
class Solution { public: bool checkPowersOfThree(int n) { while (n) { if (n % 3 == 2) return false; n /= 3; } return true; } };
以上就是C++ LeetCode1780判断数字是否可以表示成三的幂的和的详细内容,更多关于C++ LeetCode判断数字三的幂和的资料请关注我们其它相关文章!
赞 (0)