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;
    }
};