P184 报数

描述#

定义一种数据变换方式，将连续相同的一段数字，用它的数量和这个数字组合起来表示。比如对于字符串 "111221"，它是由 3 个连续的 1，2 个连续的 2，以及 1 个 1 组成，因此它变换出来的下一个字符串就是 "312211"。从字符串 "1" 开始，使用这种方式不断向后变换，就可以得到一个字符串序列：

"1", "11", "21", "1211", "111221", ...

现在给你一个整数 n，你要返回这个序列中的第 n 项。

注意，n 从 1 开始算起，也就是说在这个序列中，第 1 项是字符串 "1"。

代码#

public class AlgoCasts {

  // Time: O(1.3^n), Space: O(1.3^n)
  // Time: O(2^n), Space: O(2^n)
  public String countAndSay(int n) {
    if (n < 1) return null;
    String s = "1";
    for (int i = 1; i < n; ++i) {
      int cnt = 1;
      StringBuilder sb = new StringBuilder();
      for (int p = 0; p < s.length(); ++p) {
        if (p+1 < s.length() && s.charAt(p) == s.charAt(p+1)) {
          ++cnt;
        } else {
          sb.append(cnt).append(s.charAt(p));
          cnt = 1;
        }
      }
      s = sb.toString();
    }
    return s;
  }

}