Question

38. 外观数列

English Version

题目描述

给定一个正整数 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" 的描述如下图：

 

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

 

提示：

• 1 <= n <= 30

解法

方法一

class Solution:
  def countAndSay(self, n: int) -> str:
    s = '1'
    for _ in range(n - 1):
      i = 0
      t = []
      while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
          j += 1
        t.append(str(j - i))
        t.append(str(s[i]))
        i = j
      s = ''.join(t)
    return s

class Solution {
  public String countAndSay(int n) {
    String s = "1";
    while (--n > 0) {
      StringBuilder t = new StringBuilder();
      for (int i = 0; i < s.length();) {
        int j = i;
        while (j < s.length() && s.charAt(j) == s.charAt(i)) {
          ++j;
        }
        t.append((j - i) + "");
        t.append(s.charAt(i));
        i = j;
      }
      s = t.toString();
    }
    return s;
  }
}

class Solution {
public:
  string countAndSay(int n) {
    string s = "1";
    while (--n) {
      string t = "";
      for (int i = 0; i < s.size();) {
        int j = i;
        while (j < s.size() && s[j] == s[i]) ++j;
        t += to_string(j - i);
        t += s[i];
        i = j;
      }
      s = t;
    }
    return s;
  }
};

func countAndSay(n int) string {
  s := "1"
  for k := 0; k < n-1; k++ {
    t := &strings.Builder{}
    i := 0
    for i < len(s) {
      j := i
      for j < len(s) && s[j] == s[i] {
        j++
      }
      t.WriteString(strconv.Itoa(j - i))
      t.WriteByte(s[i])
      i = j
    }
    s = t.String()
  }
  return s
}

function countAndSay(n: number): string {
  let s = '1';
  for (let i = 1; i < n; i++) {
    let t = '';
    let cur = s[0];
    let count = 1;
    for (let j = 1; j < s.length; j++) {
      if (s[j] !== cur) {
        t += `${count}${cur}`;
        cur = s[j];
        count = 0;
      }
      count++;
    }
    t += `${count}${cur}`;
    s = t;
  }
  return s;
}

use std::iter::once;

impl Solution {
  pub fn count_and_say(n: i32) -> String {
    (1..n)
      .fold(vec![1], |curr, _| {
        let mut next = vec![];
        let mut slow = 0;
        for fast in 0..=curr.len() {
          if fast == curr.len() || curr[slow] != curr[fast] {
            next.extend(once((fast - slow) as u8).chain(once(curr[slow])));
            slow = fast;
          }
        }
        next
      })
      .into_iter()
      .map(|digit| (digit + b'0') as char)
      .collect()
  }
}

const countAndSay = function (n) {
  let s = '1';

  for (let i = 2; i <= n; i++) {
    let count = 1,
      str = '',
      len = s.length;

    for (let j = 0; j < len; j++) {
      if (j < len - 1 && s[j] === s[j + 1]) {
        count++;
      } else {
        str += `${count}${s[j]}`;
        count = 1;
      }
    }
    s = str;
  }
  return s;
};

using System.Text;
public class Solution {
  public string CountAndSay(int n) {
    var s = "1";
    while (n > 1)
    {
      var sb = new StringBuilder();
      var lastChar = '1';
      var count = 0;
      foreach (var ch in s)
      {
        if (count > 0 && lastChar == ch)
        {
          ++count;
        }
        else
        {
          if (count > 0)
          {
            sb.Append(count);
            sb.Append(lastChar);
          }
          lastChar = ch;
          count = 1;
        }
      }
      if (count > 0)
      {
        sb.Append(count);
        sb.Append(lastChar);
      }
      s = sb.ToString();
      --n;
    }
    return s;
  }
}