0338. Counting Bits =================== 题目信息 -------- :题号: 0338 :难度: Easy :主题: 非负整数、二进制表示、置位计数、结果数组 :原题: `LeetCode 0338 `_ :重点: 统计范围包含 0 和 n、结果下标就是对应整数、前导零不影响置位数量 题目重述 -------- 给定非负整数 ``n``,返回长度为 ``n+1`` 的整数数组 ``answer``。对每个 ``i``(``0 <= i <= n``),``answer[i]`` 等于整数 ``i`` 的二进制表示中数值为 ``1`` 的位数。 ``n`` 位于 ``[0, 10^5]``。结果必须从整数 ``0`` 开始按数值顺序排列,不能只返回总数或仅处理 ``1`` 到 ``n``;``0`` 的二进制置位数为 ``0``。进阶问题要求总体 ``O(n)`` 时间且避免对每个整数调用内置位计数函数。 自建示例 -------- 包含多个不同置位数: .. code-block:: text 输入:n = 6 输出:[0, 1, 1, 2, 1, 2, 2] 解释:0 到 6 的二进制分别为 0、1、10、11、100、101、110,对应置位数如输出所示。 只处理整数零: .. code-block:: text 输入:n = 0 输出:[0] 解释:结果仍需包含下标 0 对应的计数。 去掉最低位或最低置位 ---------------------- 整数 ``i`` 右移一位后,二进制表示相当于去掉原来的最低位,因此 ``bits[i] = bits[i >> 1] + (i & 1)``。右侧的 ``i >> 1`` 一定小于 ``i``,所以按下标从小到大填表时状态已经可用;``i & 1`` 只补回被移走的最低位是否为 1。 该关系同时处理了偶数和奇数,并把 ``bits[0] = 0`` 作为唯一基础,不需要对每个数重新扫描所有二进制位。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector countBits(int n) { std::vector bits(n + 1, 0); for (int i = 1; i <= n; ++i) { bits[i] = bits[i >> 1] + (i & 1); } return bits; } }; 代码分析 -------- 每个 ``bits[i]`` 只依赖一个更小的下标和一次最低位判断,结果数组下标直接对应整数本身,包含零的边界也由初始化覆盖。时间复杂度为 ``O(n)``,额外空间为 ``O(n)``;没有对每个整数调用独立的位计数过程。