Count and Say

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.

Note: The sequence of integers will be represented as a string.

Solution: 

n = 1时，打印一个1。

n = 2时，看n=1那一行，念：1个1，所以打印：11。

n = 3时，看n=2那一行，念：2个1，所以打印：21。

n = 4时，看n=3那一行，念：一个2一个1，所以打印：1211。

以此类推。(注意n是从1开始的）

所以构建当前行的字符串要依据上一行的字符串。“跑完循环之后记得把最后一个字符也加上，因为之前只是计数而已。”

时间复杂度是O(n*串的长度)，空间复杂度是O(串的长度)。

public class Solution {
    public String countAndSay(int n) {
        if(n <= 0)
            return "";
        
        String curStr = "1";
        for(int i = 2; i <= n; i++) {
            int count = 1;
            StringBuilder res = new StringBuilder();
            for(int j = 1; j < curStr.length(); j++) {
                if(curStr.charAt(j) == curStr.charAt(j - 1)) {
                    count++;
                    
                }else {
                    res.append(count);
                    res.append(curStr.charAt(j - 1));
                    count = 1;
                }
            }
            res.append(count);
            res.append(curStr.charAt(curStr.length() - 1));
            curStr = res.toString();
        }
        return curStr;
    }
}

Amazon 面筋题: 
Array Length encoding: 给定binary数组(比如[1010]), 计算每个digit数量, 返回这种形式([11011101]).
读法为 数字+次数,有点类似lc的count and say,不过不是String是int数组而已
Solution:
用一个数组helper[0,  0]来记录1和0出现的次数。
Runtime complexity O(n), constant space.

public static ArrayList count(int[] n) {
    ArrayList res = new ArrayList();
    if(n == null || n.length == 0)
        return res;
  
    int[] helper = new int[2]; //helper[0, 0]
    for(int i = 0; i < n.length; i++) {
        if(n[i] == 1) {
            if(helper[0] > 0) {
                res.add(0);
                res.add(helper[0]);
                helper[0] = 0;
            }
            helper[1] = helper[1] + 1;  
        }else if(n[i] == 0){
            if(helper[1] > 0) {
                res.add(1);
                res.add(helper[1]);
                helper[1] = 0;
            }
            helper[0] = helper[0] + 1;  
        }
    }
  
    if(helper[0] > 0) {
        res.add(0);
        res.add(helper[0]);
        helper[0] = 0;
    }else if(helper[1] > 0) {
        res.add(1);
        res.add(helper[1]);
        helper[1] = 0;
    }
  
    return res;
 }