LeetCode 338. Counting Bits

每日題。最近遇到位元運算頻率真高，無論是每日或是周賽。

題目

輸入整數n，以陣列表示0~n的數字各以二進位表示有幾個1。

整數	二進位	1數量
> 0	0	0
> 1	1	1
> 2	10	1
> 3	11	2
> 4	100	1
> 5	101	2
> 6	110	2
> 7	111	3
> 8	1000	1

解法

一個數字num要求1的數量的話，就是每次num模2取餘數，然後除num/2，直到num=0為止。
因為會有重複計算，所以可以用DP的方式完成。

class Solution:
    def countBits(self, n: int) | List[int]:
        dp = [0]*(n+1)
        for i in range(1, n+1):
            dp[i] = dp[i >> 1]+(i & 1)

        return dp

根據上方的表可以找出規律，base cases是dp[0]=0和dp[1]=1，可以發現每次將先前的n個dp結果全部+1，可以得到接下來n個答案。
| 回合數 | 十進位整數 | 二進位1數量 | | —— | —————– | —————– | | 1 | [0,1] | [0,1] | | 2 | [0,1,2,3] | [0,1,1,2] | | 3 | [0,1,2,3,4,5,6,7] | [0,1,1,2,1,2,2,3] |

那麼只要在dp陣列長度不足(n+1)時將其擴增，直到超過為止。最後回傳dp前(n+1)結果就是答案。

class Solution:
    def countBits(self, n: int) | List[int]:
        dp = [0]
        while len(dp) <= n:
            dp += [x+1 for x in dp]
        return dp[:n+1]