38.外观数列

链接：38.外观数列
难度：Medium
标签：字符串
简介：给定一个正整数 n ，输出外观数列的第 n 项。

题解 1 - typescript

• 编辑时间：2021-10-15
• 执行用时：80ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：递归层级。

function countAndSay(n: number): string {
  return findNext();
  function findNext(str = '1', level = n): string {
    if (level === 1) return str;
    let next = '';
    for (let i = 0, l = str.length; i < l; i++) {
      const ch = str[i];
      let cnt = 1;
      while (i < l - 1 && str[i + 1] === ch) {
        i++;
        cnt++;
      }
      next += cnt + ch;
    }
    return findNext(next, level - 1);
  }
}

题解 2 - c

• 编辑时间：2021-11-30
• 执行用时：4ms
• 内存消耗：6.4MB
• 编程语言：c
• 解法介绍：递归对每一层进行处理。

#define MAX 20000
char *dfs(char *str, int cnt) {
    if (cnt == 1) return str;
    int len = strlen(str), idx = 0;
    char next[MAX];
    for (int i = 0; i < len; i++) {
        char ch = str[i];
        int cnt = 1;
        while (i + 1 < len && ch == str[i + 1]) {
            ++i;
            ++cnt;
        }
        idx += sprintf(next + idx, "%d", cnt);
        next[idx++] = ch;
    }
    next[idx] = '\0';
    return dfs(next, cnt - 1);
}
char * countAndSay(int n){
    return dfs("1", n);
}

题解 3 - cpp

• 编辑时间：2021-12-20
• 内存消耗：6.5MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    string countAndSay(int n) {
        string str = "1";
        while (--n) {
            string next = "";
            for (int i = 0, n = str.size(); i < n; i++) {
                char ch = str[i];
                int cnt = 1;
                while (i + 1 < n && str[i + 1] == ch) i++, cnt++;
                while (cnt) {
                    next += cnt % 10 + '0';
                    cnt /= 10;
                }
                next += ch;
            }
            str = next;
        }
        return str;
    }
};