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;

復(fù)雜度分析

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)容，更多關(guān)于C++ LeetCode判斷數(shù)字三的冪和的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

詳解設(shè)計模式中的模板方法模式及在C++中的使用
這篇文章主要介紹了設(shè)計模式中的模板方法模式及在C++中的使用,模板方法將邏輯封裝到一個類中,并采取組合(委托)的方式解決這個問題,需要的朋友可以參考下
2016-03-03
c++ vector造成的內(nèi)存泄漏問題
這篇文章主要介紹了c++ vector造成的內(nèi)存泄漏問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2023-08-08
OpenCV?通過Mat遍歷圖像的方法匯總
對圖像中的所有點或特殊點進行運算，所以遍歷圖像就顯得很重要，如何高效的遍歷圖像是一個很值得探討的問題，本文給大家?guī)砹硕喾N方法操作OpenCV?通過Mat遍歷圖像，感興趣的朋友一起看看吧
2022-02-02
C++?STL容器詳解之紅黑樹部分模擬實現(xiàn)
本文主要對紅黑樹進行了詳細介紹，并對其核心功能進行了模擬實現(xiàn)。文中的代碼對我們的學(xué)習(xí)或工作有一定的價值，感興趣的小伙伴可以了解一下
2021-12-12
C++超詳細講解析構(gòu)函數(shù)
既然在創(chuàng)建對象時有構(gòu)造函數(shù)（給成員初始化），那么在銷毀對象時應(yīng)該還有一個清除成員變量數(shù)據(jù)的操作咯，析構(gòu)函數(shù)與構(gòu)造函數(shù)功能相反，析構(gòu)函數(shù)不是完成對象的銷毀，局部對象銷毀工作是由編譯器完成的。而對象在銷毀時會自動調(diào)用析構(gòu)函數(shù)，完成類的一些資源清理工作
2022-06-06
C++深入淺出講解希爾排序算法的實現(xiàn)
希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。本文會以圖解的方式詳細介紹希爾排序的基本思想及其代碼實現(xiàn)
2022-05-05
C 語言基礎(chǔ)教程(我的C之旅開始了)[五]
C 語言基礎(chǔ)教程(我的C之旅開始了)[五]...
2007-02-02
詳解C++ 引用
這篇文章主要介紹了C++ 引用的相關(guān)資料，文中示例代碼非常詳細，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下
2020-07-07
關(guān)于c++編譯protobuf時提示LNK2001 無法解析的外部符號的問題
這篇文章主要介紹了關(guān)于c++編譯protobuf時提示LNK2001 無法解析的外部符號的問題,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-12-12
C++深入講解引用的特點及與指針的區(qū)別
引用是C++一個很重要的特性,顧名思義是某一個變量或?qū)ο蟮膭e名，對引用的操作與對其所綁定的變量或?qū)ο蟮牟僮魍耆葍r,這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識點,需要的朋友可以參考下
2022-05-05