Leetcode-报数

作者 : 开心源码 本文共1437个字,预计阅读时间需要4分钟 发布时间: 2022-05-13 共260人阅读

0.题目

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

字符串报数写作
1一个一11
11两个一21
21一个二, 一个一1211
1211一个一,一个二, 两个一111221
111221三个一,两个二, 一个一312211
312211一个三,一个一, 两个二,两个一13112211
给定一个正整数 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

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Leetcode-报数

发表回复