leetCode38.CountandSay字符串

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.

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

根据规律可以写出后面的：

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
 10.   13211311123113112211

思路：

1.用2个串来替换存储记录result，tmp。

2.记录当前值n，获取当前值最大连续长度m。

3.tmp串追加"m",再追加"n"。

代码如下：

class Solution {
public:
    string countAndSay(int n) {
    	if (--n < 0)
    		return "";
    	string result = "1";
    	string tmp;  //临时串
    	int step = 1;//步长
    	char cur;    //当前元素
    	while (n)
    	{
    		cur = result[0];
    		for (int i = 0; i < result.size(); i++)
    		{
    			if ( i+1 < result.size() && result[i] == result[i + 1])
    			{
    				step++;
    			}
    			else
    			{
    				stringstream stepStream;
    				stepStream << step;
    				string stepStr = stepStream.str();
    				tmp.append(1,stepStr[0]);
    				tmp.append(1,cur);
    				step = 1;
    				cur = result[i + 1];
    			}
    		}
    		swap(result, tmp);
    		tmp = "";
    		n--;
    	}
    	return result;
    }
};

2016-08-10 17:24:26

网站栏目：leetCode38.CountandSay字符串
分享URL：http://6mz.cn/article/iehejh.html