38. Count and Say

问题描述

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.

题目意思为一组数列，第1个数是1，第n个数是第n-1的计数描述，比如第3个数是21，描述就是“1个2,1个1”，即1211，第4个数就是1211，第5个数就是“1个1,1个2,2个1”，即111221，同理，第6个数是312211,可不要以为数列里只有2和1。

解题思路

初始条件为1，有：f(1)=1,f(n) = countAndSay(f(n-1))，countAndSay即计数函数，使用递归即可解决。

代码

class Solution {
public:
    string countAndSay(int n) {
        if(n<=1) {
        	return "1";
        }
        // 获取上一个数，开始给它计数 
        string last = countAndSay(n-1);
        int count = 1;
        char pos = last[0];
        string current = "";
        for(int i=1;i<last.length();i++) {
        	if(pos==last[i]) {
	        	count++;
	        } else {
        		current += count+'0';
        		current += pos;
        		count=1;
        		pos = last[i];
        	}
        }
		current += count+'0';
		current += pos;
        return current;
    }
};