题目介绍

题干：
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

示例1：
输入：n = 1
输出："1"
解释：这是一个基本样例。

示例2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

---

题解思路

首先你得明白这道题的意思，其实就是每后一个字符串来描述前面哪一个字符串的每位数字的个数所组成新的字符串

首先想到的就是既然这个字符串数组是固定的，那当然可以直接枚举，把前几项列出来，因为说明了范围

所以当你还在一个一个试的时候，你就会发现答题区的大佬们早就开始整活了，直接“面向测试用例编程”，直接肝到第30个

看着那细细的滑动条，我就知道枚举的话估计得写到明年，所以就开始另辟蹊径

我自己想到的就是常规思路，新建一个字符串数组，将字符串自动生成存进去，两个循环就完事

当我去看解答的时候发现官方并没有答案，确实也是常事了，只是这样不知道那个才是优秀的解答

总结发现，用递归实现的性能和优雅程度是很不错的，而且思路清晰，所以目前看起来是最优解

---

正确代码

class Solution {
    public String countAndSay(int n) {
        		if (n == 1) {
			return "1";
		}
		String str = countAndSay(n - 1);
		StringBuffer stringBuffer = new StringBuffer();
		int len = str.length();
		
		int start = 0;
		for (int i = 1; i <= len; i++) {
			if (i == len) {
				stringBuffer.append(i - start).append(str.charAt(start));
			}else if (str.charAt(i) != str.charAt((start))) {
				stringBuffer.append(i - start).append(str.charAt(start));
				start = i;
			}
		}
		return stringBuffer.toString();
    }
}

---

总结

当然从时间和空间复杂度来说，暴力枚举的O(1)是递归望尘莫及的，可是优美的解法确实是算法题的魅力

代码中用的StrignBuffer而并不是String，因为Sting是无法修改的，所以在递归中很耗费空间去复制

而StringBuffer生命的是可变对象，对于重复的修改操作更节约时间和提升效率，这两个属性都不是基本属性哦

灵活运用每个类的特性是算法调优所必须掌握的，文章如果存在问题或者有更好的题解，希望大佬斧正和评论，各自努力，你我最高处见