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].
题目大意：
给一个数字，比如5，那么5之前所有的整数的每个二进制表示中1的个数。
思路：
| 数字 | 二进制表示 | 二进制中1的个数 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 10 | 1 |
| 3 | 11 | 2 |
| 4 | 100 | 1 |
| 5 | 101 | 2 |
| 6 | 110 | 2 |
| 7 | 111 | 3 |
| 8 | 1000 | 1 |
| 9 | 1001 | 2 |
| 10 | 1010 | 2 |
| 11 | 1011 | 3 |
| 12 | 1100 | 2 |
| 13 | 1101 | 3 |
| 14 | 1110 | 3 |
| 15 | 1111 | 4 |
| 16 | 10000 | 1 |
代码如下：
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result;
if(num == 0)
{
result.push_back(0);
return result;
}
if(num == 1)
{
result.push_back(0);
result.push_back(1);
return result;
}
result.push_back(0);
result.push_back(1);
int temp = 2;
for(int i = 2; i <=num ; i++)
{
if(i == temp*2)
temp *= 2;
result.push_back(result[i-temp] + 1);
}
return result;
}
};2016-09-01 18:57:26
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
