欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python數(shù)據(jù)結(jié)構(gòu)leetcode338比特位計數(shù)算法

 更新時間：2022年06月10日 11:33:47   作者：悲戀花丶無心之人  
這篇文章主要介紹了力扣刷題中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)容，更多關于python數(shù)據(jù)結(jié)構(gòu)比特位計數(shù)算法的資料請關注腳本之家其它相關文章！

相關文章

最新評論