LeetCode 338. 比特位计数

2024-01-10 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

LeetCode CodeTop 简单已解决 2-5 字节跳动 LeetCode 75

题目描述

✅ 338. 比特位计数

题意分析

给一个非负整数 n，要求返回一个长度为 n + 1 的数组 ans，其中 ans[i] 是整数 i 的二进制表示里 1 的个数。注意下标是从 0 到 n 闭区间，所以数组长度是 n + 1 而不是 n。

题目要的不是某一个数的位计数，而是从 0 到 n 全部数的位计数。这个「批量求解」的形式是整道题的关键信号：单独算每个数需要 $O(\log i)$，总共 $O(n \log n)$；而既然要算的是一整段连续的整数，相邻的数之间必然存在结构上的联系，可以复用已经算过的结果。看到「求某个范围内所有数的某个函数值」，就该往递推方向想。

进阶要求写得很直白：不用内置的位计数函数（如 Integer.bitCount、math/bits.OnesCount），并且做到一趟 $O(n)$。这条要求把「调库」和「逐个数拆位」两条路都堵死了，剩下的只能是复用子结果。

数据范围是 0 <= n <= 10^5，规模不大，但结果数组本身就要占 $n+1$ 个位置，所以空间下界注定是 $O(n)$，能优化的只有额外空间。

边界是 n = 0：此时要返回长度为 1 的数组 [0]，而不是空数组。任何从 i = 0 开始做转移的写法都要保证 ans[0] 是 0 而非去读越界的下标。

解法：动态规划状态转移

核心思路

朴素做法是对每个 i 单独数一遍二进制位，比如反复 i & 1 再 i >>= 1，或者用 i & (i - 1) 逐个消去最低位的 1。前者是 $O(n \log n)$，后者虽然常数更小但仍不是线性。瓶颈很明确：每个数都从零开始拆位，完全没有利用「更小的数已经算过」这个事实。

观察二进制的构造方式：把整数 i 的二进制串去掉最低位，剩下的部分恰好就是 i >> 1 的二进制串。也就是说 i 的比特由「i >> 1 的全部比特」加上「一个最低位」组成。而最低位是 0 还是 1，可以用 i & 1 一次取出。

于是得到状态定义：dp[i] 表示整数 i 的二进制表示中 1 的个数，转移方程是 dp[i] = dp[i >> 1] + (i & 1)。

这个转移之所以合法，是因为 i >> 1 严格小于 i（对所有 i >= 1 成立），所以按 i 从小到大枚举时，被依赖的状态一定已经算好了。这是无后效性的直接体现，也是可以只用一层循环、不需要任何额外判断的原因。

基准状态是 dp[0] = 0：0 的二进制里没有 1。Java 和 Go 的数组默认初始化恰好就是 0，所以这一行不需要显式写，循环直接从 i = 1 开始即可——从 1 开始也顺便避免了 i = 0 时读 dp[0] 自己形成的自依赖。

顺带一提，还有一个等价的转移 dp[i] = dp[i & (i - 1)] + 1，它依赖的是「消去最低位 1 之后的数」。两者复杂度相同，i >> 1 的版本更直观、也更容易在白板上解释，是面试中的首选。

解题步骤

开一个长度为 n + 1 的数组：下标 0 到 n 都要有位置，写成 new int[n] 会在最后一步越界。这个数组既是 dp 表也是最终答案，不需要额外的返回容器。

依赖数组默认值 dp[0] = 0 作为基准：0 没有任何 1。Java 的 int[] 与 Go 的 make([]int, ...) 都会零初始化，所以不必显式赋值；但要理解这一步是有意为之的基准状态，而不是碰巧。

循环从 i = 1 到 i <= n，正序枚举：正序是必需的，因为 dp[i] 依赖下标更小的 dp[i >> 1]；倒序会读到还未计算的格子，整张表变成 0。从 1 而不是 0 开始，是为了避开 0 >> 1 == 0 的自依赖。

执行 dp[i] = dp[i >> 1] + (i & 1)：i >> 1 去掉最低位得到一个更小的数，它的 1 的个数已知；i & 1 取出被去掉的那一位，是 1 就加 1、是 0 就加 0。注意 Java 里 & 的优先级低于 +，括号不能省，否则会被解析成 dp[i >> 1] + i 再与 1 做与运算。

循环结束直接返回 dp：它已经就是题目要求的数组，不需要再复制或转换。

以 n = 5 走一遍。

初始：dp = [0,0,0,0,0,0]，其中 dp[0] = 0 是有效的基准值，其余待填。

i = 1（二进制 1）：i >> 1 = 0，dp[0] = 0；i & 1 = 1。dp[1] = 0 + 1 = 1。正确，1 里有一个 1。

i = 2（二进制 10）：i >> 1 = 1，dp[1] = 1；i & 1 = 0。dp[2] = 1 + 0 = 1。10 确实只有一个 1——它就是 1 左移一位，个数不变。

i = 3（二进制 11）：i >> 1 = 1，dp[1] = 1；i & 1 = 1。dp[3] = 1 + 1 = 2。

i = 4（二进制 100）：i >> 1 = 2，dp[2] = 1；i & 1 = 0。dp[4] = 1。

i = 5（二进制 101）：i >> 1 = 2，dp[2] = 1；i & 1 = 1。dp[5] = 2。

返回 [0,1,1,2,1,2]，与题目样例一致。可以看到每一步依赖的下标（0、1、1、2、2）都严格小于当前下标，正序枚举保证了它们都已就绪。

再看边界 n = 0：数组长度为 1，循环条件 1 <= 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)$，其中 $n$ 是上界。只有一层循环，每轮做一次移位、一次按位与、一次加法和一次数组读写，全是常数操作。相比逐个数拆位的 $O(n \log n)$，省下的正是「重新数低位」的那部分。

空间复杂度：$O(1)$ 额外空间。长度 n + 1 的数组是题目要求的返回值，不计入额外开销；除它之外只用了循环变量 i。dp 表与答案数组合二为一，这是本题写法上最省事的一点。

关键点总结

「求一段连续整数上某个函数的全部取值」时，先找相邻或成倍数关系的数之间的递推，往往能把每个数的 $O(\log i)$ 计算摊成 $O(1)$。这是位运算与 DP 结合类题目的通用切入点。

二进制的天然递归结构是 i = (i >> 1) * 2 + (i & 1)，也就是「高位部分 + 一个最低位」。把这个分解写出来，转移方程就自己浮现了，不需要死记。

判断 dp 能否单层正序循环，只要确认被依赖的下标严格小于当前下标：这里 i >> 1 < i 对所有 i >= 1 成立，所以一层循环足够。

让返回数组直接充当 dp 表，是这类「答案本身就是一整张表」的题目的标准写法，能省掉一次拷贝；面试时顺口点出「dp 数组即答案」会显得思路清晰。

位运算符在 Java/Go 里的优先级都低于算术运算符，涉及 +、- 与 &、|、^ 混用时一律加括号，这条经验能避免大量沉默的逻辑错误。

面试时若被追问其他写法，可以给出 dp[i] = dp[i & (i - 1)] + 1（消去最低位的 1）作为等价解，并说明两者都是 $O(n)$、区别只在于依赖的子状态不同。

易错点总结

数组开成 new int[n]：n = 2 时最后一轮写 dp[2] 直接数组越界；即使不越界，返回的长度也比要求少一个。

括号漏写成 dp[i >> 1] + i & 1：Java 里 + 优先于 &，表达式变成 (dp[i>>1] + i) & 1，n = 5 会返回 [0,1,1,0,1,1]，结果全被压成 0 或 1。

循环倒序枚举 for (int i = n; i >= 1; i--)：dp[i >> 1] 读到的是尚未计算的 0，n = 5 会返回 [0,1,0,1,0,1]，只有 i & 1 那一项生效。

循环从 i = 0 开始：0 >> 1 还是 0，dp[0] = dp[0] + 0 虽然结果碰巧不变，但把基准状态写成了自依赖；一旦转移里改成 + 1 之类的形式就会立刻出错，属于埋雷写法。

循环条件写成 i < n：dp[n] 永远保持 0，n = 3 会返回 [0,1,1,0] 而不是 [0,1,1,2]，末位总是错的。

用 i / 2 但在负数场景下与 >> 1 混淆：本题 n 非负所以两者等价，但一旦被面试官改成处理负数，-3 >> 1 是 -2 而 -3 / 2 是 -1，行为分叉；养成对无符号语义用 >>> 或明确约束范围的习惯。

直接调用 Integer.bitCount(i) 填表：进阶要求明确禁止内置位计数函数，面试中会被要求重写；而且这掩盖了本题真正要考的递推观察。

对每个 i 用 while (x != 0) { cnt += x & 1; x >>= 1; } 现场数位：结果正确但复杂度是 $O(n \log n)$，没达到题目要求的线性，属于「能过但答不好」。

误以为 dp[i] = dp[i-1] + 1：相邻整数的 1 的个数并无这种关系，i = 4 时 dp[3] = 2 但 dp[4] = 1，会得到单调递增的错误结果。

n = 0 时返回空数组：正确答案是长度为 1 的 [0]，返回空数组会直接判错。

相似题目

题目	难度	考察点
191. 位1的个数	简单	只求单个数，用 `n & (n-1)` 逐次消去最低位的 1，无递推可复用
剑指 Offer 15. 二进制中1的个数	简单	与 191 同题，Java 需注意输入按无符号处理
LCR 003. 比特位计数	简单	与本题同题，可直接套用
461. 汉明距离	简单	先异或再数 1，把两数比较问题归约成单数位计数
477. 汉明距离总和	中等	两两异或会超时，改成按位统计 0 和 1 的个数再相乘
1356. 根据数字二进制下 1 的数目排序	简单	位计数只是排序的键，重点在自定义比较器的多级排序
190. 颠倒二进制位	简单	同样逐位处理，但要边取位边把结果左移拼接，还需处理固定 32 位宽
231. 2 的幂	简单	等价于判断 1 的个数是否恰为 1，可用 `n & (n-1) == 0` 一步解决
136. 只出现一次的数字	简单	用异或的自反性消去成对元素，考的是位运算性质而非逐位统计
面试题 05.07. 配对交换	简单	用奇偶位掩码分别取出后错位合并，是位运算的分组操作