题目描述
题目链接:38. Count and Say
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"
or11
.11
is read off as"two 1s"
or21
.21
is read off as"one 2
, thenone 1"
or1211
.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.
例子
例子 1
Input: 1 Output: “1” Explanation: This is the base case.
例子 2
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 > 1
时,进入循环过程,对每一次循环从前往后遍历上一个字符串(current
)并统计连续相同的字符按题目要求(次数 + 对于字符)加至新字符串(next
)中,遍历一遍旧字符串后(这里注意要将末尾剩余的一部分也加至next
中)将current
赋值为next
,重复进如下一循环
代码如下:
#include <string>
class Solution {
public:
std::string countAndSay(int n) {
std::string current = "1";
int step = 1;
while (step < n) {
step++;
std::string next = "";
int count = 1;
for (int i = 0; i < current.length() - 1; i++) {
if (current[i] == current[i + 1]) {
count++;
} else {
next += std::to_string(count) + current[i];
count = 1;
}
}
next += std::to_string(count) + current.back();
current = next;
}
return current;
}
};
- 时间复杂度: O(n * k) k 为最长字符串长度
- 空间复杂度: O(k) k 为最长字符串长度
GitHub 代码同步地址: 38.CountAndSay.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客:Leetcode-Solutions