题目描述

题目链接：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" 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 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