leetCode 38. Count and Say 字元串

38. Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:

<code>1, 11, 21, 1211, 111221, ...</code>

<code>1</code> is read off as <code>"one 1"</code> or <code>11</code>.

<code>11</code> is read off as <code>"two 1s"</code> or <code>21</code>.

<code>21</code> is read off as <code>"one 2</code>, then <code>one 1"</code> or <code>1211</code>.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

根據規律可以寫出後面的：

思路：

1.用2個串來替換存儲記錄result，tmp。

2.記錄目前值n，擷取目前值最大連續長度m。

3.tmp串追加"m",再追加"n"。

代碼如下：

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

29

30

31

32

33

34

35

36

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>string countAndSay(</code><code>int</code> <code>n) {</code>

<code>        </code><code>if</code> <code>(--n &lt; 0)</code>

<code>            </code><code>return</code> <code>""</code><code>;</code>

<code>        </code><code>string result = </code><code>"1"</code><code>;</code>

<code>        </code><code>string tmp;  </code><code>//臨時串</code>

<code>        </code><code>int</code> <code>step = 1;</code><code>//步長</code>

<code>        </code><code>char</code> <code>cur;    </code><code>//目前元素</code>

<code>        </code><code>while</code> <code>(n)</code>

<code>        </code><code>{</code>

<code>            </code><code>cur = result[0];</code>

<code>            </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; result.size(); i++)</code>

<code>            </code><code>{</code>

<code>                </code><code>if</code> <code>( i+1 &lt; result.size() &amp;&amp; result[i] == result[i + 1])</code>

<code>                </code><code>{</code>

<code>                    </code><code>step++;</code>

<code>                </code><code>}</code>

<code>                </code><code>else</code>

<code>                    </code><code>stringstream stepStream;</code>

<code>                    </code><code>stepStream &lt;&lt; step;</code>

<code>                    </code><code>string stepStr = stepStream.str();</code>

<code>                    </code><code>tmp.append(1,stepStr[0]);</code>

<code>                    </code><code>tmp.append(1,cur);</code>

<code>                    </code><code>step = 1;</code>

<code>                    </code><code>cur = result[i + 1];</code>

<code>            </code><code>}</code>

<code>            </code><code>swap(result, tmp);</code>

<code>            </code><code>tmp = </code><code>""</code><code>;</code>

<code>            </code><code>n--;</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>};</code>

2016-08-10 17:24:26

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1836606