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) 时间且避免对每个整数调用内置位计数函数。

自建示例

包含多个不同置位数:

输入:n = 6
输出:[0, 1, 1, 2, 1, 2, 2]
解释:0 到 6 的二进制分别为 0、1、10、11、100、101、110,对应置位数如输出所示。

只处理整数零:

输入:n = 0
输出:[0]
解释:结果仍需包含下标 0 对应的计数。

去掉最低位或最低置位

整数 i 右移一位后,二进制表示相当于去掉原来的最低位,因此 bits[i] = bits[i >> 1] + (i & 1)。右侧的 i >> 1 一定小于 i,所以按下标从小到大填表时状态已经可用;i & 1 只补回被移走的最低位是否为 1。

该关系同时处理了偶数和奇数,并把 bits[0] = 0 作为唯一基础,不需要对每个数重新扫描所有二进制位。

C++ 实现

class Solution {
public:
    std::vector<int> countBits(int n) {
        std::vector<int> 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);没有对每个整数调用独立的位计数过程。