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 |
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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;
}
};
|
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1845319
