小編給大家分享一下leetcod如何實(shí)現(xiàn)比特位計(jì)數(shù)，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)歡迎來(lái)電：18982081108，為您提供成都網(wǎng)站建設(shè)網(wǎng)頁(yè)設(shè)計(jì)及定制高端網(wǎng)站建設(shè)服務(wù)，創(chuàng)新互聯(lián)網(wǎng)頁(yè)制作領(lǐng)域10年，包括雨棚定制等多個(gè)領(lǐng)域擁有豐富的營(yíng)銷推廣經(jīng)驗(yàn)，選擇創(chuàng)新互聯(lián)，為網(wǎng)站保駕護(hù)航。

一、題目?jī)?nèi)容

給定一個(gè)非負(fù)整數(shù) num。對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。

示例 1:

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

示例 2:

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

進(jìn)階:

給出時(shí)間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時(shí)間O(n)內(nèi)用一趟掃描做到嗎？
要求算法的空間復(fù)雜度為O(n)。
你能進(jìn)一步完善解法嗎？要求在C++或任何其他語(yǔ)言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來(lái)執(zhí)行此操作。

二、解題思路

動(dòng)態(tài)規(guī)劃，i>>1指的是i右移一位，這樣的話i的最低位會(huì)被去掉，因此i與i>>1相當(dāng)于比較最后一位是否為1；

當(dāng) i 的最低位為0，則 i 和i >> 1中1的個(gè)數(shù)是一樣的，因?yàn)?不算進(jìn)計(jì)算1的個(gè)數(shù)；

否則，最低位為1，1相當(dāng)于被抹掉了，因此 i >> 1中1的個(gè)數(shù)加1就是i 中1的個(gè)數(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如何實(shí)現(xiàn)比特位計(jì)數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！