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
,我們稱(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)文章!
- C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官
- C/C++實(shí)現(xiàn)獲取系統(tǒng)時(shí)間的示例代碼
- C++ LeetCode1805字符串不同整數(shù)數(shù)目
- C++ LeetCode1775通過(guò)最少操作次數(shù)使數(shù)組和相等
- C++ LeetCode1812判斷國(guó)際象棋棋盤(pán)格子顏色
- C++ LeetCode300最長(zhǎng)遞增子序列
- C++?LeetCode1827題解最少操作使數(shù)組遞增
- C/C++題解LeetCode1295統(tǒng)計(jì)位數(shù)為偶數(shù)的數(shù)字
相關(guān)文章
OpenCV使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤的方法詳解
這篇文章主要為大家詳細(xì)介紹了OpenCV如何使用稀疏光流實(shí)現(xiàn)視頻對(duì)象跟蹤功能,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,需要的可以參考一下2023-02-02C語(yǔ)言中while與do-while的介紹與注意事項(xiàng)
對(duì)于C語(yǔ)言中的while與do-while,相信很多都再熟悉不過(guò)了,最近在工作中就用到了,所以想著總結(jié)一下,方便自己或者有需要的朋友們參考借鑒,文中通過(guò)示例代碼介紹的很詳細(xì),感興趣的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2016-10-10詳解C語(yǔ)言常用的一些轉(zhuǎn)換工具函數(shù)
這篇文章主要介紹了C語(yǔ)言常用的一些轉(zhuǎn)換工具函數(shù),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11C++ Boost Container庫(kù)示例詳細(xì)講解
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù),作為標(biāo)準(zhǔn)庫(kù)的后備,是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一,是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)2022-11-11Qt+OpenCV實(shí)現(xiàn)目標(biāo)檢測(cè)詳解
這篇文章主要介紹了如何利用Qt和OpenCV中自帶xml文件實(shí)現(xiàn)目標(biāo)檢測(cè),文中的實(shí)現(xiàn)過(guò)程講解詳細(xì),感興趣的小伙伴可以動(dòng)手試一試2022-03-03C語(yǔ)言使用廣度優(yōu)先搜索算法解決迷宮問(wèn)題(隊(duì)列)
這篇文章主要介紹了C語(yǔ)言使用廣度優(yōu)先搜索算法解決迷宮問(wèn)題,結(jié)合迷宮問(wèn)題分析了C語(yǔ)言隊(duì)列廣度優(yōu)先搜索算法的相關(guān)使用技巧,需要的朋友可以參考下2017-09-09