题目描述

给定一个非负整数 $num$，对于所有的 $i$，$0 \le i \le num$，计算出 $i$ 的二进制表示中1的个数。

进一步：

• 计算量是 $O(nlogn)$ 的算法很简单，你能否想出计算量是 $O(n)$ 的算法?
• 空间复杂度只能是 $O(n)$；
• 不可以使用C++中的__builtin_popcount等内建函数；

样例

输入：5
输出：[0,1,1,2,1,2]。

算法

(动态规划) $O(n)$

令f[i]表示 $i$ 的二进制表示中1的个数。
则f[i]可以由f[i/2]转移过来，$i$ 的二进制表示和 $\lfloor i/2 \rfloor$ 的二进制表示除了最后一位都一样，所以f[i] = f[i/2] + (i&1);

时间复杂度分析：总共有 $n$ 个状态，每个状态进行转移的计算量是 $O(1)$，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> f(num + 1, 0);
        for (int i = 1; i <= num; i ++ )
            f[i] = f[i >> 1] + (i & 1);
        return f;
    }
};