C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和
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
,我們稱這個(gè)整數(shù) y
是三的冪。
方法一:二進(jìn)制枚舉
題目分析
解題思路
那么,我們直接開辟一個(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)文章
OpenCV使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤的方法詳解
這篇文章主要為大家詳細(xì)介紹了OpenCV如何使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤功能,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,需要的可以參考一下2023-02-02C語言中while與do-while的介紹與注意事項(xiàng)
對(duì)于C語言中的while與do-while,相信很多都再熟悉不過了,最近在工作中就用到了,所以想著總結(jié)一下,方便自己或者有需要的朋友們參考借鑒,文中通過示例代碼介紹的很詳細(xì),感興趣的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧。2016-10-10C++ Boost Container庫示例詳細(xì)講解
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫,作為標(biāo)準(zhǔn)庫的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一,是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11Qt+OpenCV實(shí)現(xiàn)目標(biāo)檢測(cè)詳解
這篇文章主要介紹了如何利用Qt和OpenCV中自帶xml文件實(shí)現(xiàn)目標(biāo)檢測(cè),文中的實(shí)現(xiàn)過程講解詳細(xì),感興趣的小伙伴可以動(dòng)手試一試2022-03-03C語言使用廣度優(yōu)先搜索算法解決迷宮問題(隊(duì)列)
這篇文章主要介紹了C語言使用廣度優(yōu)先搜索算法解決迷宮問題,結(jié)合迷宮問題分析了C語言隊(duì)列廣度優(yōu)先搜索算法的相關(guān)使用技巧,需要的朋友可以參考下2017-09-09