Leetcode-报数

0.题目

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。

输入	输出	报数	写作
1	1	一个一	11
2	11	两个一	21
3	21	一个二, 一个一	1211
4	1211	一个一，一个二, 两个一	111221
5	111221	三个一，两个二, 一个一	312211
6	312211	一个三，一个一, 两个二，两个一	？

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

核心就是按顺序从左到右统计每个数字出现的个数，遇到不同的，则用${count}${number}表示上一次的统计。

1.递归解

 var countAndSay = function(n) {
      if (n == 1) {
        return "1";
      }

      let last = countAndSay(n - 1);

      let list = [...last];

      let count = 1;
      let str = "";
      for (let i = 0; i < list.length - 1; i++) {
        if (list[i] == list[i + 1]) {
          count++;
        } else {
          str += count + "" + list[i];
          count = 1;
        }
      }
      str += `${count}${list[list.length - 1]}`;
      return str;
    };

因为使用 list[i] == list[i + 1]作判定，所以在for循环结束后需要 str += `${count}${list[list.length - 1]}`; 处理最后一次的统计，实际开发容易忽略，改进如下:

   var countAndSay = function(n) {
      if (n == 1) {
        return "1";
      }

      let last = countAndSay(n - 1);

      let list = [...last];

      let str = "";
      for (let i = 0, count = 1; i < list.length; i++) {
        if (list[i] == list[i + 1]) {
          count++;
        } else {
          str += `${count}${list[i]}`;
          count = 1;
        }
      }

      return str;
    };

尽管遍历到最后一个元素 list[i] == list[i + 1] 中的 list[i + 1] 必定是undefined，但不会引发错误，反而执行了最后一次统计的逻辑。

2.双重for循环解法

这种正向推理的案例用递归处理，在逻辑有些绕，毕竟要先一层一层深入到n 等于1，在一层一层回到n等于5

var countAndSay = function(n) {
    let s = '1'
    for (let i = 1; i < n; i++) {
        let result = ''
        for (let i = 1, currentChar = s[0], currentCount = 1; i <= s.length; i++) {
            if (s[i] === currentChar) {
                currentCount++
            } else {
                result += `${currentCount}${currentChar}`
                currentChar = s[i]
                currentCount = 1
            }
        }
        s = result
    }
    return s
};

3.正则解

上述对数字的统计正则也可以做到。

   var countAndSay = function(n) {
      let prev = "1";
      for (let i = 1; i < n; i++) {
        prev = prev.replace(/(\d)\1*/g, (item) => `${item.length}${item[0]}`);
      }
      return prev;
    };

4. 做成数组

对于结果固定的答案，下面的解法也值得参考，或是用一些记忆函数，比如lodash的memoize

image.png

视频地址