NIKO'S BLOG
0%

外观数列解题思路

发表于

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

1
2
3
4
5
6
7
8
9
10
1       
11
21
1211
111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

外观数列前5项枚举如下：，下面的文字比较清晰的解释了什么是外观数列。这同时也是leetcode的第38题。题目要求给定一个正整数 n ，输出外观数列的第 n 项。官网给出了如下的解题思路，我将按照这个解题思路逐步拆解实现这个算法：

思路梳理

以3322251这个数为例，我们要计算这个数的下一项可以分以下几步走

  1. 把这个数转化成一个二维数组[['3', '3'], ['2', '2', '2'], ['5'], ['1']，注意这个二维数组的每一项内部数组的元素都是一样的。我们把这个函数记为strToArr(str)，稍后实现。
  2. 遍历这个二维数组，二维数组的每一项我们记为item，把每一项的item.length + item[0]拼接而来的字符串就是我们要求的下一项。我们把这个函数记为arrToStr(arr)，稍后实现。

上面的步骤只是完成了已知第n - 1项求第n项的算法，那完整的解题步骤就需要用到递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n
 * @return {string}
 */
const countAndSay = (n) => {
    const strToArr = (str) => {}
    const arrToStr = (arr) => {}
    if (n === 1) return '1'
    while (n > 1) {
        const prev = countAndSay(n - 1)
        return arrToStr(strToArr(prev))
    }
}

接下来只需要实现上面两个步骤预先占坑的两个函数就好了。

实现strToArr(str)

还是以3322251为例，我们来梳理下思路

  1. 先转成数组['3', '3', '2', '2', '2', '5', '1']
  2. 先构建一个空的二维数组[[]]，遍历数组，初始的时候把当前项push到空的二维数组中得到[['3']]，后续的遍历用当前项和二维数组内最后一项数组的最后一项比较。如果相等，就push到这个inner数组中，比如[['3', '3']]，如果不相等，构建一个新的包裹当前项的数组，push到outer数组中，比如[['3', '3'], ['2']]
  3. 遍历完成后return第2部构建的二维数组。

如果你熟悉Array.prototype.reduce的用法，会发现这个过程很适合用reduce来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const strToArr = (str) => {
    // 字符串转数组然后调用reduce,初始值是一个二维数组
    return str.split('').reduce((acc, cur) => {
        // acc是个二维数组，取最后一项
        const lastItemOfAcc = acc[acc.length - 1]
        if(!lastItemOfAcc.length || lastItemOfAcc[lastItemOfAcc.length - 1] === cur) {
            // 1. 如果acc最后一项是空数组（初始值）
            // 2. 或者acc最后一项的最后一项与当前项cur相等
            // 3. 则向acc最后一项push当前项cur
            lastItemOfAcc.push(cur)
        } else {
            // 否则，向acc push一个新的数组，数组是[cur]
            acc.push([cur])
        }
        return acc
    }, [[]])
}

实现arrToStr(arr)

这一步比较简单，就是用forEach拼接字符串：

1
2
3
4
5
6
7
const arrToStr = (arr) => {
    let str = ''
    arr.forEach(item => {
        str += (item.length + item[0])
    })
    return str
}

完整代码

至此所有步骤都已完成，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {number} n
 * @return {string}
 */
const countAndSay = function(n) {
    // 把字符串转成二维数组 '3322251' -> [['3', '3'], ['2', '2', '2'], ['5'], ['1']]
    const strToArr = (str) => {
        // 字符串转数组然后调用reduce,初始值是一个二维数组
        return str.split('').reduce((acc, cur) => {
            // acc是个二维数组，取最后一项
            const lastItemOfAcc = acc[acc.length - 1]
            if(!lastItemOfAcc.length || lastItemOfAcc[lastItemOfAcc.length - 1] === cur) {
                // 1. 如果acc最后一项是空数组
                // 2. 或者acc最后一项的最后一项与当前项cur相等
                // 3. 则向acc最后一项push当前项cur
                lastItemOfAcc.push(cur)
            } else {
                // 否则，向acc push一个新的数组，数组是[cur]
                acc.push([cur])
            }
            return acc
        }, [[]])
    }
    // 把二维数组转成结果字符串 [['3', '3'], ['2', '2', '2'], ['5'], ['1']] -> '23321511'
    const arrToStr = (arr) => {
        let str = ''
        arr.forEach(item => {
            str += (item.length + item[0])
        })
        return str
    }
    if (n === 1) return '1'
    while (n > 1) {
        // 获取前一项
        const prev = countAndSay(n - 1)
        const arr = strToArr(prev)
        return arrToStr(arr)
    }
};