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].
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. 题解：通过一个一个列出来找规律，dp[0] = 0;
dp[1] = dp[0] + 1;
dp[2] = dp[0] + 1;
dp[3] = dp[1] +1;
dp[4] = dp[0] + 1;
dp[5] = dp[1] + 1;
dp[6] = dp[2] + 1;
dp[7] = dp[3] + 1;
dp[8] = dp[0] + 1;
再转换一下dp[0] = 0;
dp[1] = dp[1 - 1] + 1;
dp[2] = dp[2 - 2] + 1;
dp[3] = dp[3 - 2] +1;
dp[4] = dp[4 - 4] + 1;
dp[5] = dp[5 - 4] + 1;
dp[6] = dp[6 - 4] + 1;
dp[7] = dp[7 - 4] + 1;
dp[8] = dp[8 - 8] + 1;
可以发现规律，被减数就是数组下标，减数从1开始，下标每到2的幂次方，减数就变成那个数，代码如下：