LeetCode38-报数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/count-and-say/

中文链接：https://leetcode-cn.com/problems/count-and-say/

题目详述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1
2
3
4
5
1. 1
2. 11
3. 21
4. 1211
5. 111221

1 被读作 “one 1” (“一个一”) , 即 11。
11 被读作 “two 1s” (“两个一”）, 即 21。
21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

1
2
输入: 1
输出: "1"

示例 2:

1
2
输入: 4
输出: "1211"

题目详解

  • 第一个数为 1，后面的数都是由前面一个数按照规则递推出来的。
  • 统计连续相同的字符个数，当前所有计数加上字符连接起来构成了下一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00038 {

    public String countAndSay(int n) {
        String s = "1";
        while (--n != 0) {
            s = getNext(s);
        }
        return s;
    }

    private String getNext(String s) {
        StringBuilder sb = new StringBuilder();
        int length = s.length();
        for (int i = 0, cnt = 0; i < length; ++i) {
            ++cnt;
            if (i + 1 == length || s.charAt(i) != s.charAt(i + 1)) {
                sb.append(cnt).append(s.charAt(i));
                cnt = 0;
            }
        }
        return sb.toString();
    }
}