leetcod如何實現(xiàn)比特位計數(shù)

小編給大家分享一下leetcod如何實現(xiàn)比特位計數(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]

進階:

給出時間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時間O(n)內(nèi)用一趟掃描做到嗎？
要求算法的空間復(fù)雜度為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)

以上是“l(fā)eetcod如何實現(xiàn)比特位計數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！