题目描述
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 <br> 1 is read off as "one 1" or 11. <br> 11 is read off as "two 1s" or 21. <br> 21 is read off as "one 2, then one 1" or 1211. <br> Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
Note: Each term of the sequence of integers will be represented as a string.
Example1:
Input: 1
Output: “1”
Explanation: This is the base case.
Example2:
Input: 4
Output: “1211”
Explanation: For n = 3 the term was “21” in which we have two groups “2” and “1”, “2” can be read as “12” which means frequency = 1 and value = 2, the same way “1” is read as “11”, so the answer is the concatenation of “12” and “11” which is “1211”.
解题思路
- 先要理解下题意。
- 题意是n=1时输出字符串1；
- n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；
- n=3时，由于上次字符是11，有2个1，所以输出21；
- n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。
- 依次类推，写个countAndSay(n)函数返回字符串。
- 其实算法很简单，就是对于前一个数，找出相同元素的个数，把个数和该元素存到新的 string 里。用一个循环进行表示即可
class Solution {
public:
string countAndSay(int n) {
if(n <= 0){
return "";
}
string res = "1";
while(--n){
string cur = "";
for(int i = 0; i < res.size(); i++){
int cnt = 1;
while(i + 1 < res.size() && res[i] == res[i + 1]){
cnt++;
i++;
}
cur += to_string(cnt) + res[i];
}
res = cur;
}
return res;
}
};
