LeetCode 1780. 判断一个数字是否可以表示成三的幂的和（位运算）

Michael阿明

发布于 2021-09-06 02:10:05

63200

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

系数每一位是 0 或者 1，用数据范围内的二进制数枚举系数的组合

class Solution {
public:
    bool checkPowersOfThree(int n) {
        int s = (1<<15);
        vector<int> pow3(16, 1);
        for(int i = 1; i <= 15; i++)
            pow3[i] = pow3[i-1]*3;
        for(int i = 0; i <= s; i++) 
        {	// 系数是 i 
            int num = 0;
            for(int j = 0; j <= 15; j++)
            {
                if(1&(i>>j))//第 j 位系数 是 1
                    num += pow3[j];
            }
            if(num == n)
                return true;
        }
        return false;
    }
};

292 ms 5.9 MB C++

从最大的位开始减

class Solution {
public:
    bool checkPowersOfThree(int n) {
        int s = (1<<15);
        vector<int> pow3(16, 1);
        for(int i = 1; i <= 15; i++)
            pow3[i] = pow3[i-1]*3;
        for(int i = 15; i >= 0; --i)
        {	
            if(n >= pow3[i])
                n -= pow3[i];
        }
        return n==0;
    }
};