力扣题目链接: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;
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; } };
class Solution { public: bool checkPowersOfThree(int n) { while (n) { if (n % 3 == 2) return false; n /= 3; } return true; } };