LeetCode 338. 比特位计数
题目描述
题意分析
对每个整数
i = 0..n，统计它的二进制表示中有多少个1，并把数量放在答案下标i处。包含0和n两个端点，因此结果长度是n+1。如果逐个数扫描所有二进制位，会反复统计相同的高位部分。这里要一次得到连续一段整数的结果，可以复用更小数的答案，在一趟扫描中完成，也不需要内置位计数函数。
解法：动态规划状态转移
核心思路
[!blue]
定义
dp[i]为整数i中二进制1的个数。把i写成2q+r，其中q = i>>1、r = i&1。二进制上，i就是在q的末尾追加一位r：偶数追加0，奇数追加1。追加的最低位为
0时，1的数量不变；为1时，数量恰好多一个。因此有转移dp[i] = dp[i>>1] + (i&1)，无需重新扫描i的全部位。基础状态
dp[0] = 0。对任何正数i，都有i>>1 < i，所以按1..n递增填表时，依赖的状态已经算好。由基础状态逐个递推，每个位置都得到准确计数，结果数组本身就是状态表。
解题步骤
- 分配长度为
n+1的零值数组，初始的dp[0]已是正确答案。- 从
i = 1遍历到n，读取dp[i>>1]，再加上最低位(i&1)。- 返回
dp。若n == 0，循环不执行，结果仍包含下标0对应的一个零。
代码实现
class Solution {
// 利用关系 dp[i] = dp[i >> 1] + (i & 1)。
public int[] countBits(int n) {
int[] dp = new int[n + 1];
// 零是基础状态，正数依赖去掉最低位后的更小下标
for (int i = 1; i <= n; i++) {
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}
}
func countBits(n int) []int {
// 利用关系 dp[i] = dp[i >> 1] + (i & 1)。
dp := make([]int, n+1)
// 零是基础状态，正数依赖去掉最低位后的更小下标
for i := 1; i <= n; i++ {
dp[i] = dp[i>>1] + (i & 1)
}
return dp
}
复杂度分析
- 时间复杂度：$O(n+1)$，每个输出位置只做常数次位运算和数组访问，满足一趟线性扫描的进阶要求；输出本身就有 $n+1$ 项。
- 空间复杂度：返回数组为 $O(n+1)$，除此之外仅 $O(1)$。
关键点总结
[!green]
- 右移得到去掉最低位后的整数，按位与
1得到被去掉的那一位，两部分恰好组成原数的全部二进制位。- 状态依赖始终指向更小下标，正序计算就能直接复用结果。
(i & 1)的括号明确最低位是单独计算的增量，避免与加法优先级混淆。
易错点总结
[!yellow]
- 倒序会读到尚未完成的较小状态。
- 数组只开
n项会漏掉上界位置。- 把转移写成前一个数加一，无法处理进位清掉多个一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 191. 位1的个数 | 简单 | 原题只统计一个数的1，本题连续求0到n，可复用较小状态避免逐个重新计数。 |
| 461. 汉明距离 | 简单 | 异或先定位两数不同位，再用位计数得到汉明距离。 |
| 137. 只出现一次的数字 II | 中等 | 按位统计重复模式并重建答案；本题利用去掉最低置位或右移结果递推计数，该题各位计数对三取模。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！