Leetcode Count and Say 数数列数字

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 n^th sequence.

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

这个是facebook的面试题，题目不好理解。

这样说会比较清楚：

其实就是一个数列n=1的时候数列为1； n=2，数列为11，n=3数列为21；n=4数列为1211；n=5数列是111221

n=2的时候数数列1有什么数字； n=3的时候数数列2有什么数字； n=4的时候数数列3有什么数字……

我的解法，利用两个临时string，数一个string存入另外一个，如此反复。

和leetcode上的一个算法差不多，时间复杂度应该是一样的。

不过运行时间却是快上差不多一倍，具体原因其实我也不清楚了。

class Solution {
public:
	string countAndSay(int n) 
	{
		if (n == 0) return "";
		string str = "1";
		for (int i = 1; i < n; i++)
		{
			char ch = '0';
			string str2 = "";
			int counting = 0;
			for (int j = 0; j < str.length(); j++)
			{
				if (str[j] == ch) counting++;
				else
				{
					if (counting > 0)
						str2 = str2 + char(counting + '0') +ch;
					counting = 1;
					ch = str[j];
				}
			}
			str2 = str2 + char(counting + '0') +ch;
			str = str2;
		}
		return str;
	}
};

下面是leetcode上比较不错的算法：

http://discuss.leetcode.com/questions/217/count-and-say

class Solution {
public:
	string getNext(string &s) 
	{
		if(s == "") return "1";
		string temp = "";
		for(int i = 0; i < s.size(); i++) {
			int cnt = 1;
			while(i+1 < s.size() && s[i] == s[i+1]) {
				i++;
				cnt++;
			}
			stringstream ss;
			ss << cnt;
			temp += ss.str();
			temp += s[i];
		}
		return temp;
	}
	string countAndSay(int n) 
	{
		string s = "";
		if(n == 0) return s;

		for(int i = 0; i < n; i++) {
			s = getNext(s);            
		}           
		return s;
	}
};