作者：孤磊
题目来源于 LeetCode 上第 38 号问题：外观数列。题目难度为 Easy。
题目描述
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
代码语言：javascript复制1. 1
2. 11
3. 21
4. 1211
5. 1112211 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
示例 1:
代码语言：javascript复制输入: 1
输出: "1"
解释：这是一个基本样例。示例 2:
代码语言：javascript复制输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。题目解析
送迭法:当 n = 1 的时候序列为 1，n = 2的时候为 11，每一个数字对应的都是固定的，都是根据上个数字计算而来的结果。
那这样就可以利用送迭法来进行每一轮的计算，完成后将结果传递到下一轮计算过程。直到符合 n 的条件为止。
动画描述
http://mpvideo.qpic.cn/0bf2r4aakaaawaajcxvw5zpfbd6dawhqabia.f10002.mp4?dis_k=309f97173d747be12baaaceb4e616428&dis_t=1589880033
代码实现
代码语言：javascript复制// 38. 外观数列
// https://leetcode-cn.com/problems/count-and-say
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public String countAndSay(int n) {
String re;
re=digui(2,n,"1");
return re;
}
private String digui(int i ,int n,String str){
if (i>n){
return str;
}
StringBuilder stringBuilder=new StringBuilder();
char c=0;
int num=0;
for (char ch:str.toCharArray()) {
if (ch!=c){
char t= (char) (num '0');
stringBuilder.append(t);
num=0;
stringBuilder.append(c);
}
c=ch;
num ;
}
stringBuilder.append((char)(num '0'));
stringBuilder.append(c);
stringBuilder.delete(0,2);
String s=digui(i 1,n,stringBuilder.toString());
return s;
}
}复杂度分析
- 空间复杂度：O(1)
- 时间复杂度：O(1)
