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.
這道題要求充分利用前面的結(jié)果罐监，我們可以找到以下規(guī)律：
如果一個數(shù)是2的冪次弓柱，那么它1的個數(shù)就是1個
如果不是，那這個數(shù)可以拆成比他小的那個最大的2的冪次的和另一個數(shù)的和航罗，1的個數(shù)也是這兩個數(shù)中1的個數(shù)的和粥血。其中2的冪次的1的個數(shù)永遠(yuǎn)為1酿箭，另一個數(shù)的1的個數(shù)已經(jīng)計算過了七问。
比如14這個數(shù)械巡，其二進(jìn)制碼為1110讥耗，拆成8+6疹启，1000+0110喊崖。
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
var res=[];
res[0]=0;
var k=0;
for(var i=1;i<=num;i++){
if((i&(i-1))===0){
k=i;
res[i]=1;
}
else {
res[i]=1+res[i-k];
}
}
return res;
};
