338. Counting Bits


Given a non negative integer numbernum. For every numbersiin the range0 ≤ i ≤ numcalculate the number of 1's in their binary representation and return them as an array.

Example:
Fornum = 5you should return[0,1,1,2,1,2].

题目大意：

给一个数字，比如5，那么5之前所有的整数的每个二进制表示中1的个数。

思路：

数字二进制表示二进制中1的个数0001
112
10131124100151012611027111381000191001210101021110113121100213110131411103151111416100001根据上面分析的到一个规律：每达到2的i次方，就会从第一个元素开始依次加1，赋值给当前元素到下一次达到2的i+1次方的元素。


代码如下：

classSolution{public:vector<int>countBits(intnum){vector<int>result;if(num==0){result.push_back(0);returnresult;}if(num==1){result.push_back(0);result.push_back(1);returnresult;}result.push_back(0);result.push_back(1);inttemp=2;for(inti=2;i<=num;i++){if(i==temp*2)temp*=2;result.push_back(result[i-temp]+1);}returnresult;}};


2016-09-01 18:57:26