python數(shù)據(jù)結構leetcode338比特位計數(shù)算法怎么使用

這篇“python數(shù)據(jù)結構leetcode338比特位計數(shù)算法怎么使用”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“python數(shù)據(jù)結構leetcode338比特位計數(shù)算法怎么使用”文章吧。

一、題目內容

給定一個非負整數(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)內用一趟掃描做到嗎？

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

你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函數(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ù)結構leetcode338比特位計數(shù)算法怎么使用”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業(yè)資訊頻道。