靈感來源?

- 保持更新，努力學習

- python腳本學習

比特位計數

解題思路

1. 對于任意整數?x，其?1?的個數等于?x // 2?的?1?的個數加上?x % 2。
2. 狀態轉移方程：dp[x] = dp[x // 2] + (x % 2)。

   class Solution:def countBits(self, n: int) -> List[int]:dp = [0] * (n + 1)for x in range(1, n + 1):# x // 2 對應 dp[x >> 1]# x % 2 對應 x & 1dp[x] = dp[x >> 1] + (x & 1)return dp

逐行解釋

class Solution:def countBits(self, n: int) -> List[int]:# 創建結果數組，dp[x]表示數字x的二進制中1的個數# 初始時所有值都為0（因為dp[0]的1的個數為0）dp = [0] * (n + 1)# 遍歷從1到n的每個數字for x in range(1, n + 1):# 關鍵狀態轉移方程：# 1. x >> 1 等價于 x // 2（右移一位，丟棄最低位）# 2. x & 1 等價于 x % 2（獲取最低位的值）# 例如：# - 若x=5（二進制101），則x>>1=2（二進制10），x&1=1#   dp[5] = dp[2] + 1 = 1 + 1 = 2# - 若x=4（二進制100），則x>>1=2（二進制10），x&1=0#   dp[4] = dp[2] + 0 = 1 + 0 = 1dp[x] = dp[x >> 1] + (x & 1)return dp