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 <code>num = 5</code> you should return <code>[0,1,1,2,1,2]</code>.
题目大意:
给一个数字,比如5,那么5之前所有的整数的每个二进制表示中1的个数。
思路:
数字
二进制表示
二进制中1的个数
1
2
10
3
11
4
100
5
101
6
110
7
111
8
1000
9
1001
1010
1011
12
1100
13
1101
14
1110
15
1111
16
10000
根据上面分析的到一个规律:每达到2的i次方,就会从第一个元素开始依次加1,赋值给当前元素到下一次达到2的i+1次方的元素。
代码如下:
17
18
19
20
21
22
23
24
25
26
27
28
<code>class</code> <code>Solution {</code>
<code>public</code><code>:</code>
<code> </code><code>vector<</code><code>int</code><code>> countBits(</code><code>int</code> <code>num) {</code>
<code> </code><code>vector<</code><code>int</code><code>> result;</code>
<code> </code><code>if</code><code>(num == 0)</code>
<code> </code><code>{</code>
<code> </code><code>result.push_back(0);</code>
<code> </code><code>return</code> <code>result;</code>
<code> </code><code>}</code>
<code> </code><code>if</code><code>(num == 1)</code>
<code> </code><code>result.push_back(1);</code>
<code> </code><code>result.push_back(0);</code>
<code> </code><code>result.push_back(1);</code>
<code> </code>
<code> </code><code>int</code> <code>temp = 2;</code>
<code> </code><code>for</code><code>(</code><code>int</code> <code>i = 2; i <=num ; i++)</code>
<code> </code><code>if</code><code>(i == temp*2)</code>
<code> </code><code>temp *= 2;</code>
<code> </code><code>result.push_back(result[i-temp] + 1);</code>
<code> </code><code>return</code> <code>result;</code>
<code> </code><code>}</code>
<code>};</code>
本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1845319