比特位计数

一、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[i] = 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[i] = ans[i//2] else: # 奇数 ans[i] = 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[i] = 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[i] = ans[i & (i-1)] + 1 return ans