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++，这样做比前一种做法效率更低； - 运用递归解决问题时，切忌追根到底，满足递归的构造规则，即可灵活应用
- 递归比较低效，还有其他方法可以代替吗？
