🍥

Hang Zhang

genius.

Data Structure and Algorithm

Count Bits

338. 比特位计数

分析

状态定义
- 定义 f[i]：表示数字 i 的二进制表示中 1 的个数
状态转移
- 将数字 i 右移一位（即 i >> 1 ），相当于去掉最低位的二进制位
- 数字 i 中的 1 的个数可以表示为：f[i] = f[i >> 1] + (i & 1)
- f[i >> 1] ：前一个数字中 1 的个数
- i & 1：判断最低位是否为 1（若最低位为 1 ，加 1 ；否则加 0 ）
初始状态
- f[0] = 0 ：数字 0 的二进制表示中没有 1

时间复杂度

遍历从 1 到 n 的所有数字，动态规划计算 f[i]
每次计算的复杂度为 O(1) ，总复杂度为 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution
{
public:
    vector<int> countBits(int n)
    {
        // 定义结果数组，长度为 n + 1
        std::vector<int> f(n + 1);
        // 动态规划填充数组
        for (int i = 1; i <= n; ++i)
            // 根据状态转移方程计算
            f[i] = f[i >> 1] + (i & 1);
        return f;
    }
};