原题：外观数列

思路：递归

思路

1. 递归逻辑

  • 如果递归了 n 次

    1
    2
    // 终止递归，返回上一个值
    if (count === n) return value;

  • 初始化当前值，重复字符计数器

    1
    2
    let currentStr = '';
    let number = 0;

  • 根据上一个值，计算当前值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    for (let i = 0; i < value.length; i++) {
      // 如果跟上一个相同或者是一第一个字符，增加计数
      if (value.charAt(i - 1) === value.charAt(i) || number === 0) number++;
      // 如果当前字符与上一个字符不同
      else {
        // 记录重复次数
        currentStr += number;
        // 记录上一个字符
        currentStr += value.charAt(i - 1);
        // 当前字符计数置为 1
        number = 1;
      }
    }
    // 如果循环结束时还在计数，最后的计数和字符需要手动记录
    if (number) {
      currentStr += number;
      currentStr += value.charAt(value.length - 1);
    }

  • 递归

    1
    2
    // 记录递归次数，递归
    return deal(count + 1, currentStr);

    最终实现：

    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
    /**
     * @param {number} count
     * @param {string} value
     * @return {string}
     */
    function deal(count, value) {
      // 已经递归了 n 次，终止递归，返回上一个值
      if (count === n) return value;
      let currentStr = '';
      let number = 0;
      // 遍历上一个字符串
      for (let i = 0; i < value.length; i++) {
        // 如果跟上一个相同或者是一第一个字符，增加计数
        if (value.charAt(i - 1) === value.charAt(i) || number === 0) number++;
        // 如果当前字符与上一个字符不同
        else {
          // 记录重复次数
          currentStr += number;
          // 记录上一个字符
          currentStr += value.charAt(i - 1);
          // 当前字符计数置为 1
          number = 1;
        }
      }
      // 如果循环结束时还在计数，最后的计数和字符需要手动记录
      if (number) {
        currentStr += number;
        currentStr += value.charAt(value.length - 1);
      }
      // 记录递归次数，递归
      return deal(count + 1, currentStr);
    }

完整代码

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
40
/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function (n) {
  /**
   * @param {number} count
   * @param {string} value
   * @return {string}
   */
  function deal(count, value) {
    // 已经递归了 n 次，终止递归，返回上一个值
    if (count === n) return value;
    let currentStr = '';
    let number = 0;
    // 遍历上一个字符串
    for (let i = 0; i < value.length; i++) {
      // 如果跟上一个相同或者是一第一个字符，增加计数
      if (value.charAt(i - 1) === value.charAt(i) || number === 0) number++;
      // 如果当前字符与上一个字符不同
      else {
        // 记录重复次数
        currentStr += number;
        // 记录上一个字符
        currentStr += value.charAt(i - 1);
        // 当前字符计数置为 1
        number = 1;
      }
    }
    // 如果循环结束时还在计数，最后的计数和字符需要手动记录
    if (number) {
      currentStr += number;
      currentStr += value.charAt(value.length - 1);
    }
    // 记录递归次数，递归
    return deal(count + 1, currentStr);
  }
  // 初始值传 1，因为 n = 1 时需要返回 "1"，不需要进行计数
  return deal(1, '1');
};