leetCode 38. Count and Say 字符串

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.

根據(jù)規(guī)律可以寫出后面的：

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

思路：

1.用2個(gè)串來(lái)替換存儲(chǔ)記錄result，tmp。

2.記錄當(dāng)前值n，獲取當(dāng)前值最大連續(xù)長(zhǎng)度m。

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

代碼如下：

class Solution {
public:
    string countAndSay(int n) {
    	if (--n < 0)
    		return "";
    	string result = "1";
    	string tmp;  //臨時(shí)串
    	int step = 1;//步長(zhǎng)
    	char cur;    //當(dāng)前元素
    	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