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