38. Count and Say

置顶

Created At : 2021-04-07 23:57

Count:661 Views 👀 :

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return thenth term of the count-and-say sequence.

Example 1:

**Input:** n = 1
**Output:** "1"
**Explanation:** This is the base case.

Example 2:

**Input:** n = 4
**Output:** "1211"
**Explanation:**
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Constraints:

1 <= n <= 30

这道计数和读法问题还是第一次遇到，看似挺复杂，其实仔细一看，算法很简单，就是对于前一个数，找出相同元素的个数，把个数和该元素存到新的 string 里。代码如下：

class Solution {
public:
    string countAndSay(int n) {
        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;
    }
};

博主出于好奇打印出了前 12 个数字，发现一个很有意思的现象，不管打印到后面多少位，出现的数字只是由 1, 2 和3 组成，网上也有人发现了并分析了原因，参见这个帖子，前十二个数字如下：

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
3 1 1 3 1 1 2 2 2 1 2 3 2 1 1 2 1 1 1 3 1 2 2 1 1 3 1 2 1 1 3 2 1 1

Github 同步地址：

https://github.com/grandyang/leetcode/issues/38

类似题目：

Encode and Decode Strings

String Compression

参考资料：

https://leetcode.com/problems/count-and-say/

https://leetcode.com/problems/count-and-say/discuss/16000/Show-an-Answer-in-Java

https://leetcode.com/problems/count-and-say/discuss/16043/C%2B%2B-solution-easy-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️.