An appearance sequence is a sequence of integers, starting with the number 1. Each item in the sequence is a description of the preceding item.

1, 11, 21, 1211, 111221 the first term is the number 1 describing the preceding term, so this number is one, which is "one one," so let's call it "11, "which describes the preceding term, So this number is going to be 21, which is "a 2 + a 1," and that's going to be called "1211, "and that's going to be called "111221."Copy the code

The first five items of the appearance sequence are enumerated above. The following text clearly explains what the appearance sequence is. This is also problem 38 in LeetCode. Given a positive integer n, output the NTH term of the appearance sequence. The official website gives the following idea of solving the problem, and I will gradually disassemble and implement the algorithm according to this idea:

Thinking to comb

So if we take the number 3322251, and we want to calculate the next term of this number we can do it in the following steps

  1. Convert this number into a two-dimensional array[['3', '3'], ['2', '2', '2'], ['5'], ['1']Notice that each item of this two-dimensional array has the same elements inside the array. So let’s call this function thetastrToArr(str), which will be implemented later.
  2. We’re going to go through this two dimensional array, and every entry in the two dimensional array we’re going to call this oneitemLet’s take each of these termsitem.length + item[0]The concatenated string is the next item we want. So let’s call this function thetaarrToStr(arr), which will be implemented later.

The above steps only complete the algorithm for solving the NTH term given the NTH minus 1 term, so the complete step of solving the problem requires recursion:

/ * * *@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))
    }
}
Copy the code

All you need to do next is implement the two functions that are preempted in the above two steps.

implementationstrToArr(str)

Let’s take 3322251 as an example, so let’s sort out the idea

  1. Let’s turn it into an array['3', '3', '2', '2', '5', '1']
  2. Build an empty two-dimensional array[[]]To iterate through the array, initially push the current item into an empty two-dimensional array[[' 3 ']], subsequent traversals compare the current item to the last item in the array of the last item in the two-dimensional array. If it’s equal, push it into this inner array, for example[[' 3 ', '3']]If not, build a new array that wraps the current item and push it into the outer array, for example[[' 3 ', '3'], [' 2 ']]
  3. When the traversal is completereturnThe two-dimensional array built in Part 2.

If you are familiar with array.prototype. reduce, you will see that this process works well with reduce:

const strToArr = (str) = > {
    // Convert the string to an array and call Reduce. The initial value is a two-dimensional array
    return str.split(' ').reduce((acc, cur) = > {
        // acc is a two-dimensional array. Take the last item
        const lastItemOfAcc = acc[acc.length - 1]
        if(! lastItemOfAcc.length || lastItemOfAcc[lastItemOfAcc.length -1] === cur) {
            // 1. If the last item in acc is an empty array (initial value)
            // 2. Or the last item of the last acc item is equal to the current item, cur
            // 3. Push the current item to the last item in ACC
            lastItemOfAcc.push(cur)
        } else {
            // Otherwise, push a new array to acc. Array is [cur]
            acc.push([cur])
        }
        return acc
    }, [[]])
}
Copy the code

implementationarrToStr(arr)

This is an easy step: Concatenate the string with forEach:

const arrToStr = (arr) => {
    let str = ''
    arr.forEach(item => {
        str += (item.length + item[0])
    })
    return str
}
Copy the code

The complete code

So far all the steps are complete, the complete code is as follows:

/ * * *@param {number} n
 * @return {string}* /
const countAndSay = function(n) {
    / / the string into a two-dimensional array of '3322251' - > [[' 3 ', '3'], [' 2 ', '2', '2'], [' 5 '], [' 1 ']]
    const strToArr = (str) = > {
        // Convert the string to an array and call Reduce. The initial value is a two-dimensional array
        return str.split(' ').reduce((acc, cur) = > {
            // acc is a two-dimensional array. Take the last item
            const lastItemOfAcc = acc[acc.length - 1]
            if(! lastItemOfAcc.length || lastItemOfAcc[lastItemOfAcc.length -1] === cur) {
                // 1. If the last item in acc is an empty array
                // 2. Or the last item of the last acc item is equal to the current item, cur
                // 3. Push the current item to the last item in ACC
                lastItemOfAcc.push(cur)
            } else {
                // Otherwise, push a new array to acc. Array is [cur]
                acc.push([cur])
            }
            return acc
        }, [[]])
    }
    / / the two dimensional array to the result string [[' 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) {
        // Get the previous item
        const prev = countAndSay(n - 1)
        const arr = strToArr(prev)
        return arrToStr(arr)
    }
};
Copy the code