Counting Bits

發表於   |   分類於

Counting Bits

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:

For num = 5 you should return [0,1,1,2,1,2].

关键点在于找出数字二进制之间的关系：15 = 8 + 7，20 = 16 + 4这样

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> DP(num+1,0);
        DP[1] = 1;
        DP[2] = 1;
        for (int i = 3; i <= num; ++i)
        {
            int k = 1;
            while(k <= i)
            {
                k *= 2;
            }
            k /= 2;
            int l = i - k;
            if (l == 0) DP[i] = 1;
            else DP[i] = DP[k] + DP[l];
        }
        return DP;
    }
};