文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數 n ，如果你可以將 n 表示成若干個不同的三的冪之和，請你返回 true ，否則請返回 false 。

對于一個整數 y ，如果存在整數 x 滿足 $y==3^x$，我們稱這個整數 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 位系數 是 1num += 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;} };

0 ms 5.9 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1780. 判断一个数字是否可以表示成三的幂的和（位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。