各位题友大家好，@负雪明烛 又出现了。

题意

取值为 n 的「外观数列」是对取值为 n - 1 的「外观数列」的描述。

解题思路

解法一：循环

两重循环的思路是：

  • 外层循环 $i$ 负责递增 $1 .. n$；
  • 内存循环负责求当取值为 $i$ 时的外观数列。

Java 和 Python 代码如下：

  1. public class Solution {
  2.     public String countAndSay(int n) {
  3.         StringBuilder ans = new StringBuilder("1");
  4.         StringBuilder prev;
  5.         int count;
  6.         char say;
  7.         for(int i = 1; i < n; i++){
  8.             prev = ans;
  9.             ans = new StringBuilder();
  10.             count = 1;
  11.             say = prev.charAt(0);
  12.             for(int j = 1; j < prev.length(); j++){
  13.                 if(say != prev.charAt(j)){
  14.                     ans.append(count).append(say);
  15.                     count = 1;
  16.                     say = prev.charAt(j);
  17.                 }else{
  18.                     count++;
  19.                 }
  20.             }
  21.             ans.append(count).append(say);
  22.         }
  23.         return ans.toString();
  24.     }
  25. }
  1. class Solution(object):
  2.     def countAndSay(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: str
  6.         """
  7.         res = "1"
  8.         for i in range(n - 1):
  9.             prev = res[0]
  10.             count = 1
  11.             ans = ""
  12.             for j in range(1, len(res)):
  13.                 cur = res[j]
  14.                 if prev != cur:
  15.                     ans = ans + str(count) + str(prev)
  16.                     prev = cur
  17.                     count = 0
  18.                 count += 1
  19.             res = ans + str(count) + str(prev)
  20.         return res
  • 时间复杂度：$O(n * m)$，$n$ 是输入的数字，$m$ 是「外观数列」的最大长度；
  • 空间复杂度：$O(m)$。

解法二：递归

其实，按照题目描述的话，我们最容易想到的应该就是递归解法。

题目描述是：

  • countAndSay(1) = “1”
  • countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

这个意思就是想求 countAndSay(n) 的话，必须先求 countAndSay(n-1)，这就是标准的递归。

使用递归求解，一定不要用大脑去模拟递归的过程。大脑能压几个栈？

正确的做法是：记住递归函数的定义。比如本题中的递归函数 countAndSay(int n)含义是当取值为 $n$ 时的外观数列。

那么，必须先求出取值为 $n - 1$ 时的外观数列，怎么求？根据递归函数的定义，就是 countAndSay(n - 1)。至于 countAndSay(n - 1) 怎么算的，我们不用管。只要知道这个函数能给我们正确的结果就行。

我在下面的代码把 countAndSay(n - 1) 的结果即为 before，然后统计了 before 中各个数字出现的次数，就是取值为 $n$ 时的外观数列。

C++ 代码如下：

  1. class Solution {
  2. public:
  3.     string countAndSay(int n) {
  4.         if (n == 1) {
  5.             return "1";
  6.         }
  7.         string before = countAndSay(n - 1);
  8.         string res;
  9.         char cur = before[0];
  10.         int count = 1;
  11.         for (int i = 1; i < before.size(); ++i) {
  12.             if (before[i] != cur) {
  13.                 res += to_string(count) + cur;
  14.                 cur = before[i];
  15.                 count = 0;
  16.             }
  17.             count ++;
  18.         }
  19.         res += to_string(count) + cur;
  20.         return res;
  21.     }
  22. };
  • 时间复杂度：$O(n * m)$，$n$ 是输入的数字，$m$ 是「外观数列」的最大长度；

  • 空间复杂度：$O(m)$。

    刷题心得

  • 递归是最贴合本题意的解法。

  • 递归的时间复杂度和遍历是一样的，因为 $1..n$ 中的每个数字都被计算了一次。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们下期再见！