338. 比特位计数

题目

338. 比特位计数（简单）

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

不要使用内置函数来解决（例如，C++ 中的 __builtin_popcount）。

示例 1：

输入：

2

输出：

[0,1,1]

解释：
0 —> 0
1 —> 1
2 —> 10

示例 2：

输入：

5

输出：

[0,1,1,2,1,2]

解释：
0 —> 0
1 —> 1
2 —> 10
3 —> 11
4 —> 100
5 —> 101

提示：

• 0 <= n <= 10^5

思路

DP 递推：res[i] 的 1 的个数可由更小的数推出——i 为奇数时比 i - 1 多一个 1（末位是 1），i 为偶数时与 i / 2 相同（左移一位不改变 1 的个数）。两种写法等价，位运算版 res[i >> 1] + (i & 1) 更紧凑。

代码

方法一：奇偶递推

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            if i % 2 == 1:
                res[i] = res[i - 1] + 1
            else:
                res[i] = res[i // 2]
        return res

方法二：位运算

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