338 Counting Bits 比特位計(jì)數(shù)

Description:
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:

Example 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [0,1,1,2,1,2]

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

題目描述:
給定一個(gè)非負(fù)整數(shù) num。對于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i 沽瘦，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回革骨。

示例 :

示例 1:

輸入: 2
輸出: [0,1,1]

示例 2:

輸入: 5
輸出: [0,1,1,2,1,2]

進(jìn)階:

給出時(shí)間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時(shí)間O(n)內(nèi)用一趟掃描做到嗎析恋？
要求算法的空間復(fù)雜度為O(n)良哲。
你能進(jìn)一步完善解法嗎？要求在C++或任何其他語言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來執(zhí)行此操作助隧。

思路:

動(dòng)態(tài)規(guī)劃
dp[i]表示這一位對應(yīng)的整數(shù)有 n個(gè) 1
對于每一個(gè) i, i >> 1是已經(jīng)計(jì)算過的, 如果 i是偶數(shù), 則 i和 i >> 1的 1的個(gè)數(shù)相同, 如果 i是奇數(shù), 則 i比 i >> 1的 1個(gè)個(gè)數(shù)多 1, 就是加上 i % 2的結(jié)果(即 i & 1)
如 9(1001) -> 4(100), 2 -> 1
動(dòng)態(tài)轉(zhuǎn)移方程: dp[i] = dp[i >> 1] + (i & 1)
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

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

Java:

class Solution {
    public int[] countBits(int num) {
        int result[] = new int[num + 1];
        for (int i = 0; i < num + 1; i++) result[i] = result[i >> 1] + (i & 1);
        return result;
    }
}

Python:

class Solution:
    def countBits(self, num: int) -> List[int]:
        result = [0] * (num + 1)
        for i in range(num + 1):
            result[i] = result[i >> 1] + (i & 1)
        return result