leetCode 338. Counting Bits | Dynamic Programming | Medium

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&lt;</code><code>int</code><code>&gt; countBits(</code><code>int</code> <code>num) {</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; 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 &lt;=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