【算法积累】外观数列

比眉伴天荒 2022-12-18 12:56 117阅读 0赞

## LeetCode 38. 外观数列 ##

**难度** 简单

给定一个正整数`n (1 ≤ n ≤ 30)`，输出外观数列的第`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**

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

**示例2**

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

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

**解法** 字符计数  
语言：C

char* countAndSay(int n) { 
        char* ret = (char*)malloc(sizeof(char) * 5000);
        char* temp = (char*)malloc(sizeof(char) * 5000);
        ret[0] = '1';
        ret[1] = '\0';
        int len = 1;
        while (--n) { 
            int i = 0, j = 0;
            while (i < len) { 
                /* 对ret中的字符进行计数 */
                int cnt = 1;
                char ch = ret[i];
                i++;
                while (i < len && ret[i] == ch) { 
                    cnt++;
                    i++;
                }
                temp[j] = cnt + '0';
                j++;
                temp[j] = ch;
                j++;
            }
            temp[j] = '\0';
            strcpy(ret, temp);
            len = j;
        }
        return ret;
    }

语言：Python 3（递归）

class Solution:
        def countAndSay(self, n: int) -> str:
            if n == 1:
                return '1'
            pre = self.countAndSay(n - 1)
            ret = ''
            cnt = 0
            for i in range(len(pre)):
                if i == 0:
                    cnt += 1
                elif pre[i] != pre[i - 1]:
                    temp = str(cnt) + pre[i - 1]
                    ret += temp
                    cnt = 1
                elif pre[i] == pre[i - 1]:
                    cnt += 1
                if i == len(pre) - 1:
                    temp = str(cnt) + pre[i]
                    ret += temp
            return ret