C++ LeetCode1780判断数字是否可以表示成三的幂的和
LetMeFly 人气:0LeetCode 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; } };
加载全部内容