C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和
更新時間：2022年12月16日 12:01:39 作者：LetMeFly
這篇文章主要為大家介紹了C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和題解示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
LeetCode 1780.判斷一個數(shù)字是否可以表示成三的冪的和
力扣題目鏈接：leetcode.cn/problems/ch…
給你一個整數(shù) n ，如果你可以將 n 表示成若干個不同的三的冪之和，請你返回 true ，否則請返回 false 。
對于一個整數(shù) y ，如果存在整數(shù) x 滿足 y == 3x ，我們稱這個整數(shù) y 是三的冪。
方法一：二進制枚舉
題目分析
解題思路
那么，我們直接開辟一個數(shù)組，把所有的小于等于nnn的“3的冪”放入數(shù)組
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;
}
};
方法二：進制轉(zhuǎn)換
AC代碼
C++
class Solution {
public:
bool checkPowersOfThree(int n) {
while (n) {
if (n % 3 == 2)
return false;
n /= 3;
}
return true;
}
};以上就是C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和的詳細內(nèi)容，更多關于C++ LeetCode判斷數(shù)字三的冪和的資料請關注腳本之家其它相關文章！
相關文章
OpenCV使用稀疏光流實現(xiàn)視頻對象跟蹤的方法詳解
這篇文章主要為大家詳細介紹了OpenCV如何使用稀疏光流實現(xiàn)視頻對象跟蹤功能，文中的示例代碼講解詳細，具有一定的借鑒價值，需要的可以參考一下2023-02-02
樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點）按分支關系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹形象表示，本篇介紹二叉樹的遞歸與非遞歸遍歷的方法2022-06-06
對于C語言中的while與do-while，相信很多都再熟悉不過了，最近在工作中就用到了，所以想著總結(jié)一下，方便自己或者有需要的朋友們參考借鑒，文中通過示例代碼介紹的很詳細，感興趣的朋友們下面來一起學習學習吧。2016-10-10
這篇文章主要介紹了C++控制臺用定時器實例代碼，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-02-02
這篇文章主要介紹了C語言常用的一些轉(zhuǎn)換工具函數(shù),本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
這篇文章主要介紹了如何利用Qt和OpenCV中自帶xml文件實現(xiàn)目標檢測，文中的實現(xiàn)過程講解詳細，感興趣的小伙伴可以動手試一試2022-03-03
這篇文章主要介紹了C++中的數(shù)據(jù)內(nèi)存分布，主要從動態(tài)內(nèi)存管理方式，內(nèi)存泄漏等方面介紹的，文中也有相關的示例代碼,需要的朋友可以參考下2023-05-05
右值引用，一般是在深拷貝的類，實現(xiàn)移動構(gòu)造和移動賦值，能夠解決左值引用無法做到的傳返回值的效率問題，下面跟隨小編一起學習下C++11語法之右值引用的問題2022-04-04
這篇文章主要介紹了C語言使用廣度優(yōu)先搜索算法解決迷宮問題,結(jié)合迷宮問題分析了C語言隊列廣度優(yōu)先搜索算法的相關使用技巧,需要的朋友可以參考下2017-09-09