LeetCode 图解 | 38. 外观数列

你的名字 2023-03-13 03:54 74阅读 0赞

**点击关注上方“图解面试算法”，**

**设为“置顶或星标”，一起刷 LeetCode。**

![format_png][]

作者：孤磊

题目来源于 LeetCode 上第 38 号问题：外观数列。题目难度为 Easy。

# 题目描述 #

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221

`1` 被读作 "`one 1`" ("一个一") , 即 `11`。

`11` 被读作 "`two 1s`" ("两个一"）, 即 `21`。

`21` 被读作 "`one 2`", "`one 1`" （"一个二" , "一个一") , 即 `1211`。

给定一个正整数 *n*（1 ≤ n ≤ 30），输出外观数列的第 *n* 项。

注意：整数序列中的每一项将表示为一个字符串。

**示例 1:**

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

**示例 2:**

输入: 4
    输出: "1211"
    解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。

# 题目解析 #

**送迭法**:当 n = 1 的时候序列为 1，n = 2的时候为 11，每一个数字对应的都是固定的，都是根据上个数字计算而来的结果。

那这样就可以利用送迭法来进行每一轮的计算，完成后将结果传递到下一轮计算过程。直到符合 n 的条件为止。

# 动画描述 #

# 代码实现 #

// 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)

--------------------

### **推荐阅读** ###

--------------------

**今天是 『 365 刷题计划 』 第 29 天。每晚八点，一起图解一道算法题，不见不散！**

欢迎关注我的公众号“**图解面试算法**”，如果喜欢，麻烦点一下“**在看**”，转发+在看相当于打赏！

![format_png 1][]

[format_png]: /images/20230312/bf316d5ca1394300ac0e74352a688347.png
[LeetCode _ _ 42.]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb689367dc1f1a71d9abe01870a2749943f96c2d6fd67f5d591ec199c93a5955f385c1442f0c&idx=1&mid=2247483940&scene=21&sn=425f1e6a52ed27a9a5bde7ddd4145522#wechat_redirect
[LeetCode _ _ 11.]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb689363dc1f1a7593cfe4c5ed86f9222e432fb15e2b092cb7923d6ab63b80c3186289c057dc&idx=1&mid=2247483936&scene=21&sn=4f0cb75ee023c94de95bf7f4259792e0#wechat_redirect
[LeetCode _ _ 477.]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb68934bdc1f1a5dd1137668df81f4e6dde1b360af188fdfee9e61f2b8afdcbe469e3c4a77a0&idx=1&mid=2247483912&scene=21&sn=131fb6e2b4b866e59e0d62d93c904aa7#wechat_redirect
[LeetCode _ _ 661.]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb6890bcdc1f19aa41caf20f53f1c4fa208700065d0bdb9e1bb1721d46c1ace7f8667f7b8938&idx=1&mid=2247483903&scene=21&sn=c630d4a11246a8d89e9414003d5e6057#wechat_redirect
[LeetCode _ _ 1099. _ K]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb6890badc1f19aca25a19705b110113fc2f6e0b7c53f5d6996d00b100f9047b3940cca7968a&idx=1&mid=2247483897&scene=21&sn=902c40ba39eb055160b495b716d7927c#wechat_redirect
[LeetCode _ _ 169.]: http://mp.weixin.qq.com/s?__biz=MzI3NzIwMjk4OA%3D%3D&chksm=eb6890b1dc1f19a7ce6aebf788310207abf8518178564fdfa61a58fd7a01a9312c23a2368635&idx=1&mid=2247483890&scene=21&sn=142bc67d8b7ae50640e40eb58da024d1#wechat_redirect
[format_png 1]: /images/20230312/869e6416ad6f48cf8a109f8794f2e882.png