38. 外觀數(shù)列

所謂外觀數(shù)列，就是后一個數(shù)列是對前一個數(shù)列的描述。打個比方：

序列號1：  1        
序列號2：  11      這是對上一個數(shù)據(jù)1的描述，上一個數(shù)據(jù)為1個1，記做：11.
序列號3：  21      這是對上一個數(shù)據(jù)11的描述，上一個數(shù)據(jù)為2個1，記做：21.
序列號4：  1211    這是對上一個數(shù)據(jù)21的描述，上一個數(shù)據(jù)為1個2，1個1，記做：1211.
...

題目是，給出相應(yīng)的序列號，算出對應(yīng)的外觀數(shù)列。

要找序列號為n的外觀數(shù)列，那么就得知道序列號為n-1的外觀數(shù)列的值，要想知道序列號為n-1的外觀數(shù)列的值，就得知道序列號為n-2的外觀數(shù)列的值...

以此類推，很容易聯(lián)想到用遞歸，而遞歸的終止條件可以是以下兩個：

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

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

這樣做就能保證preString的長度至少大于等于2，不用做額外的判斷。preString代表上一個外觀數(shù)列的值，在下面的代碼中會提到。

然后，兩指針最初分別指向外觀數(shù)列中第0位和第1位，當(dāng)指向的元素相同時，right指針向前移動一位，否則添加對應(yīng)元素。

left和right指針的差值就是某個數(shù)字的出現(xiàn)的次數(shù)。

    // 遞歸算法
    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]) {
                // 開始構(gòu)建描述數(shù)列，此時right - left代表著中間隔了多少個相同的元素
                result.append((right - left)).append(preString[left]);
                left = right;
            }
            // 每個遍歷，right右移一位
            right++;
            // 當(dāng)達(dá)到元素的末尾時
            if (right == preString.length) {
                result.append((right - left)).append(preString[left]);
            }

        }

        return result.toString();
    }