題目
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 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 term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
分析
寫了這組字符串的前幾個(gè)潘拱，試圖找到規(guī)律。但是沒有找到明顯的規(guī)律源请，看來只能使用遞推來做了。思路很簡單缓待，就是統(tǒng)計(jì)上一個(gè)字符串中連續(xù)出現(xiàn)的字符來構(gòu)造下一個(gè)字符串亚情，重復(fù)n次即可犀被。
實(shí)現(xiàn)
class Solution {
public:
string countAndSay(int n) {
string input, output="1";
n--;
while(n--){
input = output;
output.clear();
int i=0;
while(i<input.size()){
int count=1;
char ch=input[i];
while(i+1<input.size() && input[i+1]==ch){
count++;
i++;
}
output += count + '0';
output += ch;
i++;
}
}
return output;
}
};
思考
有趣的一點(diǎn)是厕倍，對于string類型來說，使用+操作符就比使用push_back()函數(shù)快了不少尚氛。
