LeetCode 38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 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 term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: “1”
Example 2:

Input: 4
Output: “1211”
解析：
题目理解起来感觉有点别扭，下面逐一说明。
当n=1时，result=1
n=2时的result是根据前一个结果得来的，n=1时是1个1，所以写成11
n=3时，由n=2的结果得到，11这是2个1，所以写作21
n=4,n=3时的21可以读作1个2，1个1，最终写成1211
依此类推。
解法1，
由以上分析可知，当前结果是由前一个结果得到的，因此采用递归方式。
[cc lang=”C++”]
class Solution {
public:
string countAndSay(int n) {
if (n ==1)
return “1”;
string previous = countAndSay(n-1);
int len = previous.length();
string result = “”;
int count = 0;
char pre_char = ‘ ‘;
for(int index =0; index < len; index ++) { char item = previous.at(index); if(index == len-1) { if(item == pre_char) count ++; else { if(pre_char !=' ') { result += std::to_string(count); result.push_back(pre_char); } count =1; } result += std::to_string(count); result.push_back(item); }else { if (item == pre_char) count ++; else { if(pre_char != ' ') { result += std::to_string(count); result.push_back(pre_char); } count =1; pre_char = item; } } } return result; } }; [/cc] 自己写的代码感觉有点繁琐，需要判断的情况比较多。但是执行时间还好，用时4ms
解法2:
采用非递归方式
[cc lang=”C++”]
class Solution {
public:
string countAndSay(int n) {
if(n<1) return ""; string ret = "1"; for(int i=2; i<=n; i++) {//外层循环控制每一位的生成，要生成n位，依次生成前面的所有位数 string temp = ""; int count = 1; char prev = ret[0];//记录前一个元素 for(int j=1; j