比特位计数
Counting Bits
本机进度仅保存在当前浏览器
题目描述
给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回长度为 n + 1 的数组作为答案。进阶：能否用 O(n) 的一次遍历完成，不使用内置函数？
示例：n = 5，输出 [0, 1, 1, 2, 1, 2]。
解题思路
- 递推性质一：i 的二进制是 i >> 1 左移一位，1 的个数与 i >> 1 相同，末位由 i & 1 决定，故 bits[i] = bits[i >> 1] + (i & 1)。
- 递推性质二（Kernighan）：bits[i] = bits[i & (i - 1)] + 1，去掉最低位的 1 后查表。
- 两个递推都只用更小的下标，一次线性扫描完成，是"以自身数组为记忆表"的迷你 DP。
参考实现
查看参考实现Python · 建议先自行作答
def countBits(n):
bits = [0] * (n + 1)
for i in range(1, n + 1):
# i 右移一位的 1 的个数 + 最低位
bits[i] = bits[i >> 1] + (i & 1)
return bits