【HC】比特位计数

无名

一、338. 比特位计数1.1、题目描述
1.2.1、直接法： 根据191. 位1的个数（也被称为汉明重量）class Solution:    def countBits(self, num: int) -> List[int]:        ans = [0] * (num+1)         for i in range(num+1):            ans = self.popCount(i)        return ans    def popCount(self, num: int) -> int:        count = 0        while num != 0:            num = num & (num - 1)            count += 1        return count1.2.2、根据奇偶性
class Solution:    def countBits(self, num: int) -> List[int]:        ans = [0] * (num+1)         for i in range(1, num+1):            if i&1 == 0:# 偶数                ans = ans[i//2]            else:       # 奇数                ans = ans[i-1] + 1        return ans  123456789101.2.3、优化： 右移+最低位(推荐)class Solution:    def countBits(self, num: int) -> List[int]:        ans = [0] * (num+1)         for i in range(1, num+1):            tmp = i&1            ans = ans[i>>2] + tmp        return ans1.2.4、动态规划 + 最后设置位
class Solution:    def countBits(self, num: int) -> List[int]:        ans = [0] * (num+1)         for i in range(1, num+1):            ans = ans[i & (i-1)] + 1        return ans