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:
Hint:
思路：假设res[i]意味着数字i的二进制中1的个数。
i为偶数时，res[i]=res[i/2]；i为奇数时，res[i]=res[i-1]+1。
其实也可以写成这样：res[i]=res[i/2] + i%2。
代码：
i为偶数时，res[i]=res[i/2]；i为奇数时，res[i]=res[i-1]+1。
1 class Solution { 2 public: 3 vector<int> countBits(int num) { 4 vector<int> res(num+1,0); 5 int i; 6 for(i=1;i<=num;i++){ 7 if(i%2){//odd 8 res[i]=res[i-1]+1; 9 } 10 else{ 11 res[i]=res[i>>1]; 12 } 13 } 14 return res; 15 } 16 };
其实也可以写成这样：res[i]=res[i/2] + i%2。
1 class Solution { 2 public: 3 vector<int> countBits(int num) { 4 vector<int> res(num+1,0); 5 int i; 6 for(i=1;i<=num;i++){ 7 res[i]=res[i/2]+i%2; 8 } 9 return res; 10 } 11 };
原文：http://www.cnblogs.com/Deribs4/p/5720307.html