問題
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.
例子
5
111221
分析
統(tǒng)計字符串的連續(xù)重復字符
要點
盡量迭代慕购，不用遞歸
時間復雜度
O(n^2) n次迭代彤敛，每次迭代的結(jié)果字符串的長度呈線性增長能真。
空間復雜度
O(1)
代碼
class Solution {
public:
string countAndSay(int n) {
string res("1");
for (int i = 0; i < n - 1; i++)
res = say(res);
return res;
}
private:
string say(const string &str) {
string res;
char c = str[0];
int cnt = 1;
for (int i = 1; i < str.size(); i++) {
if (str[i] == c) cnt++;
else {
res += to_string(cnt) + string(1, c);
c = str[i];
cnt = 1;
}
}
res += to_string(cnt) + string(1, c);
return res;
}
};
