題目：
給定一個非負整數 n，對於每個 0 ≤ i ≤ n 的整數 i，計算其二進位表示中 1 的個數，並回傳一個長度為 n+1 的陣列 ans，其中 ans[i] 表示整數 i 中 1 的個數。

範例：

輸入: n = 5
輸出: [0,1,1,2,1,2]
解釋:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解題思路

先用最簡單的暴力法，直接拿 191 那題的答案來運用。

實作：

class Solution {
public:
    int hammingWeight(int n) {
        int bit = 0;
        int i = 0;
        int cnt = 0;
        while (n > 0) {
            bit = n % 2;
            if (bit) {
                cnt++;
            }
            n = n / 2;
            i++;
        }
        return cnt;
    }

    vector<int> countBits(int n) {
        vector<int> ret(n+1);
        for (int i = 0; i < n+1; i++) {
            int cnt = hammingWeight(i);
            ret[i] = cnt;
        }
        return ret;
    }
};

感覺可以用前一個數字的結果來計算這次的結果。

參考：
#338. Counting Bits