38.外观数列.md

LeetCode 38.外观数列

描述

「外观数列」(原报数)是一个整数序列，从数字 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"

解一 [匹配连续数字统计次数]

思路

循环上一次字符

使用一个count统计连续相同的数字出现次数

如果这一次的数字与前一个不一样（即res[i] !== res[i+1]）则该数字统计完毕 并把count重置为0

代码

var countAndSay = function(n) {
    let res = "1";
    while(--n){
        let count = 0;
        let nextStr = '';
        for(var i = 0,len = res.length; i < len; i++) {
            count++;
            if(res[i] !== res[i+1]){
                nextStr+= count+res[i];
                count = 0;
            }
        }
        res = nextStr;
    }
    return res;
};

解二 [递归]

思路

要求第n项的外观数列 先要求出 n-1项的外观数列而 n-1项的外观数列需要n-1-1的外观数列...

我们已知 第一项 即（n = 1）时外观数列为 "1" 所以出口为 如果 n == 1 则返回 "1"

拿到 n-1项的外观数列 通过上一解法求出n 项的外观数列并返回即可

代码

var countAndSay = function(n) {
    if (n === 1) return '1';
    let prevStr = countAndSay(n-1); // 先获取n-1项的外观数列
    // 统计相同连续数字出现次数
    let count = 0;
    let res = ''
    for (let i = 0; i < prevStr.length; i++) {
      count++;
      if(prevStr[i] !== prevStr[i+1]) {
        res += count + prevStr[i];
        count = 0;
      }
    }
    return res;
};