C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和

更新時(shí)間：2022年12月16日 12:01:39 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和題解示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

LeetCode 1780.判斷一個(gè)數(shù)字是否可以表示成三的冪的和

力扣題目鏈接：leetcode.cn/problems/ch…

給你一個(gè)整數(shù) n ，如果你可以將 n 表示成若干個(gè)不同的三的冪之和，請(qǐng)你返回 true ，否則請(qǐng)返回 false 。

對(duì)于一個(gè)整數(shù) y ，如果存在整數(shù) x 滿足 y == 3x ，我們稱(chēng)這個(gè)整數(shù) y 是三的冪。

方法一：二進(jìn)制枚舉

題目分析

解題思路

那么，我們直接開(kāi)辟一個(gè)數(shù)組，把所有的小于等于nnn的“3的冪”放入數(shù)組

vector<int> three(1, 1);  // 初始值是1個(gè)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;
    }
};

方法二：進(jìn)制轉(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ù)字是否可以表示成三的冪的和的詳細(xì)內(nèi)容，更多關(guān)于C++ LeetCode判斷數(shù)字三的冪和的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

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