[LintCode] 420 Count and Say 解题报告

Description
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.


Notice
The sequence of integers will be represented as a string.


Example
Given n = 5, return "111221".


思路
先解读一下题意。
当n == 1时，直接返回"1"。
当n == 2时，对n == 1返回的字符串进行数数。很显然，我们读一下"1"：1个"1"。所以我们返回"11"。
当n == 3时，对n == 2返回的"11"数数。我们读出2个"1"。于是返回"21"。
。。。
例子里当n == 5时，我们读n == 4返回的"111221"。也就是3个1，2个2，1个1。返回值"312211"。

两重循环。 第一重循环每次更新需要count and say的字符串，也就是前一次的返回值。
第二重循环对当前的字符串进行count and say。遍历字符串，在当前值不等于之前一个元素时，表示之前那个元素已经数完了。我们把那个元素的count和say更新到结果里。然后从当前元素重新初始计数。


Code

public class Solution {
    /**
     * @param n the nth
     * @return the nth sequence
     */
    public String countAndSay(int n) {
        // Write your code here
        if (n == 1) {
            return "1";
        }
        StringBuilder curr = new StringBuilder("1");
        for (int i = 2; i <= n; i++) {
            StringBuilder prev = curr;
            curr = new StringBuilder();
            int count = 1;
            char say = prev.charAt(0);
            for (int j = 1; j < prev.length(); j++) {
                if (prev.charAt(j) != say) {
                    curr.append(count).append(say);
                    count = 1;
                    say = prev.charAt(j);
                }
                else {
                    count++;
                }
            }
            curr.append(count).append(say);
        }
        
        return curr.toString();
    }
}