题目描述：
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
1. 1 2. 11 3. 21 4. 1211 5. 111221
1 被读作 "一个一", 即 11。11 被读作 "两个一", 即 21。21 被读作"一个二" , "一个一", 即 1211
要求：
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
解题思路：
从题目中的信息可以知道，当我们想要求第n项的结果时，需要先知道第n-1项的字符串;想要求出第n-1项的结果时，必须先知道第n-2项的结果......以此类推，推到第1项，第一项的结果正是"1"。所以想求第n项的结果时，可以从第一项以此往后递推。解决此题，可以使用演绎法、递归法、以及使用栈。
第一种解法：使用演绎法
describe函数是针对”上一个“结果项进行分析，然后分析求出下一个结果项的样子。
public String countAndSay(int n) {
String num = "1";
for (int i = 0; i < n - 1; i++) {
num = describe(num.toCharArray());
}
return num;
}
public static String describe(char[] chars){
StringBuilder string = new StringBuilder();
char ch = chars[0];
int temp = 1,i = 1;
while(i < chars.length){
if (chars[i] == ch)
temp++;
else{
string.append(temp).append(chars[i-1]);
ch = chars[i];
temp = 1;
}
i++;
}
string.append(temp).append(chars[i - 1]);
return string.toString();
}
第二种解法：递归
递归与上面第一种解法几乎相同，唯一不同的就是上面用的是循环，而此处采用递归的方式。
// 递归用法
public String countAndSay4(int n) {
if (n == 1)
return "1";
return describe(countAndSay4(n - 1).toCharArray());
}
public static String describe(char[] chars){
StringBuilder string = new StringBuilder();
char ch = chars[0];
int temp = 1,i = 1;
while(i < chars.length){
if (chars[i] == ch)
temp++;
else{
string.append(temp).append(chars[i-1]);
ch = chars[i];
temp = 1;
}
i++;
}
string.append(temp).append(chars[i - 1]);
return string.toString();
}
第三种解法：使用栈
栈中存储的都是相同的元素，因此栈中元素个数就表示有几个栈中元素。内循环结束之后，还有进行一次append操作是为了将出现在末尾的连续数字结果进行保存。
public String countAndSay3(int n){
if (n==1)
return "1";
Stack<Character> stack = new Stack<>();
StringBuilder string;
String res = "1";
for (int i = 1; i < n; i++) {
stack.clear();
string = new StringBuilder();
char[] chars = res.toCharArray();
for (int j = 0;j < chars.length;j++){
if (stack.isEmpty() || stack.peek() == chars[j]){
stack.push(chars[j]);
}else {
string.append(stack.size()).append(stack.peek());
stack.clear();
stack.push(chars[j]);
}
}
string.append(stack.size()).append(stack.peek());
res = string.toString();
}
return res;
}