38. 外观数列

解题过程

INFO

题目链接给定一个正整数 n ，输出外观数列的第 n 项。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列： countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(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" 要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。例如，数字字符串 "3322251" 的描述如下图：

javascript

/**
 * @link https://leetcode.cn/problems/count-and-say/
 * @title 38. 外观数列
 * @description 给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(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"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来
 * @param {number} n
 * @return {string}
 */
// 解法一
// 思路：难点在于描述前一项的数字字符，根据题意判断写出，暴力解决即可
// 第一步：初始化一个存储前一项数字字符的数组
// 第二步：遍历当前数字，描述前一项数字字符：将前一项数字字符转数组，然后遍历统计连续数字个数和对应数字拼接起来存储
// 第三步：取出最后数字字符数组对应的数字项内容
var countAndSay = function (n) {
  const numStrs = new Array(n + 1).fill('1')

  for (let i = 2; i <= n; i++) {
    const preNums = numStrs[i - 1].split('')

    let sign = 0
    let str = preNums[0]
    let numStr = ''

    for (let j = 0; j < preNums.length; j++) {
      if (str === preNums[j]) {
        sign++
      } else {
        numStr += sign + str
        str = preNums[j]
        sign = 1
      }

      if (j === preNums.length - 1) {
        numStr += sign + str
      }
    }

    numStrs[i] = numStr
  }

  return numStrs[n]
}

// 解法二
// 思路：通过递归操作，❌但是没写完，时间关系需要补充ing
var countAndSay = function (n) {
  const numStrs = new Array(n + 1).fill('1')

  const count = (num) => {
    if (num === 2) {
      numStrs[2] = '11'
      return '11'
    }
    numStrs[num] = count(num - 1)
  }

  count(n)

  return numStrs[n]
}

// 解法三
// 思路：来自题解：通过正则匹配对应的相同元素累加，很不错的思路解法
// 难点在于理解： \1表示匹配的是 所获取的第1个()匹配的引用, 如"1a11aa221".replace(/(\d)\1/g,6), 返回的是"1a6aa61",匹配了"11"和"22"; *表示匹配{0,无穷大}次,\1*就是表示\1可以出现0次或者更多次, 如"1a11aa221".replace(/(\d)\1*/g,6), 返回的是"6a6aa66",匹配了1,11,22,1
var countAndSay = function (n) {
  let lastNum = '1'

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

  return lastNum
}

// const result = countAndSay(2) // 11
// const result = countAndSay(3) // 21
// const result = countAndSay(4) // 1211
const result = countAndSay(5) // 111221
console.log(result)

解题感受

解法一很普通的解法做出来的，解法二想用递归去做的，时间关系没再去做了，解法三看了题解是一个很不错的思路，但对正则表达式比较熟悉，简单方便。其他解法比如双指针也是不错的，可惜没时间去想了

38. 外观数列 ​

解题过程 ​

解题感受 ​

优质题解 ​

38. 外观数列

解题过程

解题感受

优质题解