---

thumbnail: https://s2.ax1x.com/2019/04/05/ARfLq0.jpg
title: 38. Count and Say
toc: true
tags: leetcode
categories: leetcode
comments: true

---

题目描述：报数

报数序列是指一个整数序列，按照顺序进行报数，得到下一个数。其中前五项如下：

1.1 读作一一,所以下一项为11
2.11读作二一,所以下一项为21
3.21读作一二一一,所以下一项为1211
4.1211读作一一一二二一,所以下一项为111221
5.111221 读作三一二二一一,所以下一项为312211
...

以此类推

示例1：

Input:
       1
Output:
       "1"

示例2：

Input:
       4
Output:
       "1211"

---

分析：

• 报数是指一串序列中的某个数
• 该序列中某项的值与其前一项有关，规则如题目描述

思路：该序列中的某个值是由前一项的报数,因此具有这种回溯性质的题目，我们不妨可以采用递归的方法去做。
写递归要明确两点：终止条件和递归体

• 终止条件：当n<=1时,返回1;
• 递归体：在假定得到前一项的值后，需要对该值进行遍历，遍历时要统计连续相同字符的长度，以该数个数+该数组成新的字符串，便可得到报数。

---

java代码：

class Solution {
    public String countAndSay(int n) {
        if(n<=1) return "1";
        String preStr = countAndSay(n-1);
        String res = "";
        int len = preStr.length();
        for(int i=0;i<len;i++){
            int k = i;
            while(i+1<len&&preStr.charAt(i)==preStr.charAt(i+1)){
                i++;
            }
            res = res+ (i-k+1) + preStr.charAt(i);
        }
        return res;
    }
}

运行的时间和空间复杂度如下图：

运行时间和所用内存
总结：

• 终止条件写为n<=1，而不是n==1可以使代码更加严谨；
• 在该代码之前,确定某个字符的个数所采用的方法，并不是i-k+1,而是每次遍历时，都初始化k=0,然后在while循环体中执行k++，这样做比前一种做法效率更低；
• 运用递归解决问题时，切忌追根到底，满足递归的构造规则，即可灵活应用
• 递归比较低效，还有其他方法可以代替吗？