338. 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].
Follow up:
1.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?
2.Space complexity should be O(n).
3.Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
分析
这道题需要我们对一个数中’1’bit的数量进行统计，最最容易想到的方法就是O(n*sizeof(integer))的算法，也就是将一个数的二进制表示一位位拆开，统计1的个数，代码如下:
/*compute every bit then judge if it equals 1*/
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1,0);
for(int i=0;i<=num;i++){
for(int j=0;j<32;j++){
if(i!=0&&(i>>j)&1==1)
res[i]++;
}
}
return res;
}
};
在题目的暗示下，我们有了更好的方法，那就是将0~num的区间进行划分，分成[2-3], [4-7], [8-15]这样的区间，我们如果把0~15的二进制数中的1进行统计，如下:
0000 0
-------------
0001 1
-------------
0010 1
0011 2
-------------
0100 1
0101 2
0110 2
0111 3
-------------
1000 1
1001 2
1010 2
1011 3
1100 2
1101 3
1110 3
1111 4
发现了一个规律，从0100开始，前一半和上一个区间中的值完全相同，而后一半是上一个区间中的值依次+1。所以，我们可以尽量利用已经计算出的结果对算法进行优化。代码如下:
/*make use of what you have produced*/
class Solution {
public:
vector<int> countBits(int num) {
if(num==0)
return {0};
vector<int> res{0,1};
int k=1,i=1;
while(i<=num){
for(i=pow(2,k);i<pow(2,k+1);i++){
if(i>num)
break;
int tmp=(pow(2,k+1)-pow(2,k))/2;
if(i<pow(2,k)+tmp)
res.push_back(res[i-tmp]);
else
res.push_back(res[i-tmp]+1);
}
k++;
}
return res;
}
};
这个代码在交给OJ之后，测算出的时间似乎并不能令人满意，甚至还不如第一种暴力破解的算法。所以，参照讨论区大神的代码，我发现了更深的一个规律。
如果一个数是偶数，其含有的’1’的个数与其除以2的结果含有的‘1’的个数相同，如果是奇数，则和其除以2的结果含有的‘1’的个数再加1相同，代码如下:
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res{0};
for(int i=1;i<=num;i++){
if(i%2==0)
res.push_back(res[i/2]);
else
res.push_back(res[i/2]+1);
}
return res;
}
};
对于位运算的问题，我们只有多做题，多参阅讨论区大神的思路，才能获取到足够的经验，游刃有余地处理各类问题，希望自己能够继续保持谦逊的态度吧。
2016-10-20