38. Count and Say

[niuworld]

Question:

The count-and-say sequence is the sequence of integers beginning as >follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

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

Solution:

這道題的難點在於讀懂題目，反正我是讀了二十分鐘才明白%>_<%

1，11，21，1211，111221，...將這些數看成數列，每個元素都是由前一個元素決定。

• 第一個元素為1
• 第二個元素就要按照前一個元素"1"來進行決定，一個一，"11"
• 第三個元素由"11"來決定，兩個一，"21"
• 第四個元素由第三個元素"21"決定，一個二＋一個一，"1211"
• 第五個元素由第四個元素"1211"決定，一個一＋一個二＋兩個一，"111211"

以此類推... ...

我的代碼是採取兩個string元素，依次交替賦值。

class Solution {
public:
    string countAndSay(int n) {
       string re[2] = { "", "1"};
       int next = 0, cur = 1;
       if ( n < 2 ) return re[n];
       int len, i;
       while ( n > 1){
           i = 0;

           while( re[cur][i] ){
               len = 1;
           while( re[cur][i] == re[cur][i+1]){
               len++;
               i++;
             }
           re[next] += to_string(len) + re[cur][i];
           i++;
           }
           cur = next;
           next = 1 - cur;
           re[next].clear();
           n--;
         }
         return re[cur];
       }
};