python數(shù)據(jù)結(jié)構(gòu)leetcode338比特位計(jì)數(shù)算法
一、題目內(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++或任何其他語言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來執(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)文章
yolov5 win10 CPU與GPU環(huán)境搭建過程
這篇文章主要介紹了yolov5 win10 CPU與GPU環(huán)境搭建過程,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
Python使用turtle庫繪制小豬佩奇(實(shí)例代碼)
這篇文章主要介紹了Python使用turtle庫繪制小豬佩奇，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-01-01
這篇文章主要介紹了python requests模塊的使用解析，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下2021-04-04
Python中numpy數(shù)組的計(jì)算與轉(zhuǎn)置詳解
大家好，本篇文章主要講的是Python中numpy數(shù)組的計(jì)算與轉(zhuǎn)置詳解，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
Python使用PyMySql增刪改查Mysql數(shù)據(jù)庫的實(shí)現(xiàn)
PyMysql是Python中用于連接MySQL數(shù)據(jù)庫的一個(gè)第三方庫,本文主要介紹了Python使用PyMySql增刪改查Mysql數(shù)據(jù)庫的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01
這篇文章主要介紹了Python如何把字典寫入到CSV文件的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
Python構(gòu)建XML樹結(jié)構(gòu)的方法示例
這篇文章主要介紹了Python構(gòu)建XML樹結(jié)構(gòu)的方法,結(jié)合實(shí)例形式分析了Python創(chuàng)建與打印xml數(shù)結(jié)構(gòu)的實(shí)現(xiàn)步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
python使用pika庫調(diào)用rabbitmq交換機(jī)模式詳解
這篇文章主要介紹了python使用pika庫調(diào)用rabbitmq交換機(jī)模式詳解，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下2022-08-08
這篇文章主要介紹了python清除字符串里非數(shù)字字符的方法,涉及Python使用re模塊正則替換操作字符串的技巧,需要的朋友可以參考下2015-07-07
python pandas利用fillna方法實(shí)現(xiàn)部分自動(dòng)填充功能
這篇文章主要介紹了python pandas通過fillna方法實(shí)現(xiàn)部分自動(dòng)填充功能,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03