338. 比特位计数

一、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 count

1.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
  

1.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 ans
  

1.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