python數(shù)據(jù)結(jié)構(gòu)leetcode338比特位計(jì)數(shù)算法
一、題目?jī)?nèi)容
給定一個(gè)非負(fù)整數(shù) num。對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。
示例 1:
輸入: 2
輸出: [0,1,1]
示例 2:
輸入: 5
輸出: [0,1,1,2,1,2]
進(jìn)階:
給出時(shí)間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時(shí)間O(n)內(nèi)用一趟掃描做到嗎？
要求算法的空間復(fù)雜度為O(n)。
你能進(jìn)一步完善解法嗎？要求在C++或任何其他語(yǔ)言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來(lái)執(zhí)行此操作。
二、解題思路
動(dòng)態(tài)規(guī)劃，i>>1指的是i右移一位，這樣的話i的最低位會(huì)被去掉，因此i與i>>1相當(dāng)于比較最后一位是否為1；
當(dāng) i 的最低位為0，則 i 和i >> 1中1的個(gè)數(shù)是一樣的，因?yàn)?不算進(jìn)計(jì)算1的個(gè)數(shù)；
否則，最低位為1，1相當(dāng)于被抹掉了，因此 i >> 1中1的個(gè)數(shù)加1就是i 中1的個(gè)數(shù)；
三、代碼
class Solution:
def countBits(self, num: int) -> list:
dp = [0 for _ in range(num + 1)]
for i in range(num + 1):
i_last_num = i & 1 # 得到i的末位數(shù)字
if i_last_num == 0:
dp[i] = dp[i >> 1]
else:
dp[i] = dp[i >> 1] + i_last_num
return dp
if __name__ == '__main__':
s = Solution()
num = 5
ans = s.countBits(num)
print(ans)以上就是python數(shù)據(jù)結(jié)構(gòu)leetcode338比特位計(jì)數(shù)算法的詳細(xì)內(nèi)容，更多關(guān)于python數(shù)據(jù)結(jié)構(gòu)比特位計(jì)數(shù)算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
pandas中DataFrame的merge操作的實(shí)現(xiàn)
本文主要介紹了pandas中DataFrame的merge操作的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-07-07
這篇文章主要介紹了在Django框架中編寫Contact表單的教程,Django是Python特色各異的框架中最有人氣的一個(gè),需要的朋友可以參考下2015-07-07
Python將Excel表格按某列拆分為多個(gè)sheet實(shí)現(xiàn)過(guò)程
這篇文章主要為大家介紹了Python實(shí)現(xiàn)將Excel表格按某列拆分為多個(gè)sheet，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Python?PyQt拖動(dòng)控件對(duì)齊到網(wǎng)格的方法步驟
pyqt是一個(gè)用于創(chuàng)建GUI應(yīng)用程序的跨平臺(tái)工具包,它將python與qt庫(kù)融為一體,下面這篇文章主要給大家介紹了關(guān)于Python?PyQt拖動(dòng)控件對(duì)齊到網(wǎng)格的方法步驟,需要的朋友可以參考下2022-12-12
本篇文章給大家詳細(xì)分析了Python輸出各行命令的解釋，為初學(xué)者提供詳細(xì)的講解，有興趣的朋友參考下。2018-02-02
如何使用Python SqlAlchemy，本文為大家詳細(xì)介紹Python SqlAlchemy的使用方法，感興趣的朋友可以參考一下2016-02-02
利用python模擬sql語(yǔ)句對(duì)員工表格進(jìn)行增刪改查
這篇文章主要給大家介紹了關(guān)于利用python模擬sql語(yǔ)句實(shí)現(xiàn)對(duì)員工表格進(jìn)行增刪改查的相關(guān)資料，文中介紹了詳細(xì)的需求以及示例代碼，對(duì)大家的理解和學(xué)習(xí)具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧。2017-07-07
這篇文章主要介紹了Python利用 matplotlib 模塊繪制直方圖相關(guān)屬性和方法，具有一定的參考價(jià)值,需要的朋友可以參考一下2021-12-12
django框架使用views.py的函數(shù)對(duì)表進(jìn)行增刪改查內(nèi)容操作詳解【models.py中表的創(chuàng)建、views.py中
這篇文章主要介紹了django框架使用views.py的函數(shù)對(duì)表進(jìn)行增刪改查內(nèi)容操作,結(jié)合實(shí)例形式詳細(xì)分析了models.py中表的創(chuàng)建、views.py中函數(shù)的使用，基于對(duì)象的跨表查詢等相關(guān)操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2019-12-12
這篇文章主要為大家介紹了Python語(yǔ)法概念基礎(chǔ)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01