python數據結構leetcode338比特位計數算法

Posted on by

一、題目內容

給定一個非負整數 num。對於 0 ≤ i ≤ num 范圍中的每個數字 i ，計算其二進制數中的 1 的數目並將它們作為數組返回。

示例 1:

輸入: 2

輸出: [0,1,1]

示例 2:

輸入: 5

輸出: [0,1,1,2,1,2]

進階:

給出時間復雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時間O(n)內用一趟掃描做到嗎？

要求算法的空間復雜度為O(n)。

你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函數（如 C++ 中的 __builtin_popcount）來執行此操作。

二、解題思路

動態規劃，i>>1指的是i右移一位，這樣的話i的最低位會被去掉，因此i與i>>1相當於比較最後一位是否為1；

當 i 的最低位為0，則 i 和i >> 1中1的個數是一樣的，因為0不算進計算1的個數；

否則，最低位為1，1相當於被抹掉瞭，因此 i >> 1中1的個數加1就是i 中1的個數；

三、代碼

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的末位數字
            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數據結構leetcode338比特位計數算法的詳細內容，更多關於python數據結構比特位計數算法的資料請關註WalkonNet其它相關文章！

推薦閱讀：