每日一题篇 — leetcode38号题外观数列

38. 外观数列

所谓外观数列，就是后一个数列是对前一个数列的描述。打个比方：

序列号1：  1        
序列号2：  11      这是对上一个数据1的描述，上一个数据为1个1，记做：11.
序列号3：  21      这是对上一个数据11的描述，上一个数据为2个1，记做：21.
序列号4：  1211    这是对上一个数据21的描述，上一个数据为1个2，1个1，记做：1211.
...

题目是，给出相应的序列号，算出对应的外观数列。

要找序列号为n的外观数列，那么就得知道序列号为n-1的外观数列的值，要想知道序列号为n-1的外观数列的值，就得知道序列号为n-2的外观数列的值...

以此类推，很容易联想到用递归，而递归的终止条件可以是以下两个：

if (n == 1) return "1";

if (n == 2) return "11";

这样做就能保证preString的长度至少大于等于2，不用做额外的判断。preString代表上一个外观数列的值，在下面的代码中会提到。

然后，两指针最初分别指向外观数列中第0位和第1位，当指向的元素相同时，right指针向前移动一位，否则添加对应元素。

left和right指针的差值就是某个数字的出现的次数。

    // 递归算法
    private String getStringByCount(int n) {
        if (n == 1) return "1";

        if (n == 2) return "11";
        // 递归计算前一个元素的值 
        char[] preString = getStringByCount(n - 1).toCharArray();

        int left = 0;
        StringBuilder result = new StringBuilder();

        for (int right = 1; right < preString.length; ) {
            // 不同位上的元素不一样
            if (preString[left] != preString[right]) {
                // 开始构建描述数列，此时right - left代表着中间隔了多少个相同的元素
                result.append((right - left)).append(preString[left]);
                left = right;
            }
            // 每个遍历，right右移一位
            right++;
            // 当达到元素的末尾时
            if (right == preString.length) {
                result.append((right - left)).append(preString[left]);
            }

        }

        return result.toString();
    }