外观数列

来自Leetcode第38题外观数列

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

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 项。

---

递归+双指针

第n层依赖n-1层求出的结果,设置两个指针,pre指向字符串初始位置0,cur指向字符串1的位置,如果说str[pre] != str[cur],说明当前字符与前面紧邻的字符不等则更新此次结果,则是sb.append(count).append(str[pre]);,结束循环时,如果pre!=cur,说明两者之间的数据是相等的,仍需要append数据.

class Solution {
    public String countAndSay(int n) {
        StringBuilder sb = new StringBuilder();
        int pre = 0;
        int cur = 1;
        if(n == 1)
            return "1";
        char[] str = countAndSay(n-1).toCharArray();
        for(cur = 1 ; cur < str.length;++cur){
            if(str[pre] != str[cur]){  //当前字符与前面紧邻的字符不等则更新此次结果
                int count = cur - pre;
                sb.append(count).append(str[pre]);
                pre = cur;
            }
        }
        if(pre != cur){  //防止最后一段数相等，如果不等说明p1到cur-1这段字符串是相等的
            int count = cur - pre;
            sb.append(count).append(str[pre]);
        }
        return sb.toString();
    }
}