38. Count and Say

只要理解了题意，其实挺简单的。比如"11113222"读做“4个1，1个3，3个2”，下一个数字就是"411332"。正好最近看到某个解谜游戏中也有个类似的密码，感觉挺巧合的。。。

public class Solution {

    public String countAndSay(int n) {
        if (n <= 1)
            return "1";

        // 循环n-1次
        String init = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder sb = new StringBuilder();
            char lastChar = 0;
            int count = 0;
            // 其实就是计算一个字符会连续出现几次
            for (int j = 0; j < init.length(); j++) {
                char thisChar = init.charAt(j);
                if (count == 0 || thisChar != lastChar) {
                    if (count != 0) {
                        sb.append(count);
                        sb.append(lastChar);
                    }
                    lastChar = thisChar;
                    count = 1;
                } else if (thisChar == lastChar) {
                    count++;
                }
            }
            // 别忘了最后的这个字符
            if (count != 0) {
                sb.append(count);
                sb.append(lastChar);
            }

            init = sb.toString();
        }

        return init;
    }
}

解法还是很简单的。而且这个解法可以beat 64.4%。但我突发奇想，如果先计算n=10，再计算n=20，肯定会有很多重复计算，是否可以加个缓存？把每次计算结果缓存起来，如果命中缓存就不用计算了。于是：

public class Solution {
    // 作弊。。。全局的缓存
    private static Map<Integer, String> sayCache = new HashMap<Integer, String>();

    public String countAndSay(int n) {
        if (sayCache.containsKey(n))
            return sayCache.get(n);
        if (n <= 1)
            return "1";

        // 循环n-1次
        String init = "1";
        for (int i = 2; i <= n; i++) {
            // 先查看缓存，命中了就不用重复计算了
            if (sayCache.containsKey(i)) {
                init = sayCache.get(i);
                continue;
            }
            StringBuilder sb = new StringBuilder();
            char lastChar = 0;
            int count = 0;
            for (int j = 0; j < init.length(); j++) {
                char thisChar = init.charAt(j);
                if (count == 0 || thisChar != lastChar) {
                    if (count != 0) {
                        sb.append(count);
                        sb.append(lastChar);
                    }
                    lastChar = thisChar;
                    count = 1;
                } else if (thisChar == lastChar) {
                    count++;
                }
            }

            if (count != 0) {
                sb.append(count);
                sb.append(lastChar);
            }

            init = sb.toString();
            // 更新缓存
            sayCache.put(i, init);
        }

        return init;
    }
}

这个解法也只能beat 64.4%，几乎没什么区别。因为leetcode的test case太少了，只有18个。如果数据量变大，有缓存的版本性能应该会好很多。