摘要：前言的第一道題目，雖然分值才分，但是卻是中等難度的題目迭代器編寫一個(gè)遍歷游程編碼序列的迭代器。迭代器由初始化，其中是某個(gè)序列的游程編碼。迭代器支持一個(gè)函數(shù)，它耗盡接下來的個(gè)元素并返回以這種方式耗去的最后一個(gè)元素。

Weekly Contest 101的第一道題目，雖然分值才4分，但是卻是中等難度的題目RLE 迭代器：

編寫一個(gè)遍歷游程編碼序列的迭代器。
迭代器由RLEIterator(int[] A)初始化，其中A是某個(gè)序列的游程編碼。更具體地，對(duì)于所有偶數(shù) i，A[i] 告訴我們?cè)谛蛄兄兄貜?fù)非負(fù)整數(shù)值 A[i + 1] 的次數(shù)。
迭代器支持一個(gè)函數(shù)：next(int n)，它耗盡接下來的n個(gè)元素（n >= 1）并返回以這種方式耗去的最后一個(gè)元素。如果沒有剩余的元素可供耗盡，則 next返回-1。
例如，我們以A = [3,8,0,9,2,5]開始，這是序列 [8,8,8,5,5] 的游程編碼。這是因?yàn)樵撔蛄锌梢宰x作 “三個(gè)零，零個(gè)九，兩個(gè)五”。
示例：
輸入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
輸出：[null,8,8,5,-1]
解釋：
RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
這映射到序列 [8,8,8,5,5]。
然后調(diào)用 RLEIterator.next 4次。

.next(2) 耗去序列的 2 個(gè)項(xiàng)，返回 8?，F(xiàn)在剩下的序列是 [8, 5, 5]。

.next(1) 耗去序列的 1 個(gè)項(xiàng)，返回 8?，F(xiàn)在剩下的序列是 [5, 5]。

.next(1) 耗去序列的 1 個(gè)項(xiàng)，返回 5。現(xiàn)在剩下的序列是 [5]。

.next(2) 耗去序列的 2 個(gè)項(xiàng)，返回 -1。 這是由于第一個(gè)被耗去的項(xiàng)是 5，
但第二個(gè)項(xiàng)并不存在。由于最后一個(gè)要耗去的項(xiàng)不存在，我們返回 -1。
PS:Leetcode這次的競(jìng)賽時(shí)間是1小時(shí)45分鐘是因?yàn)楦?jìng)賽開始了10分鐘，但是題目還是看不到

其實(shí)一開始做這個(gè)題目的時(shí)候我也是一頭霧水，首先游程編碼是一個(gè)我沒接觸過的概念，其次是這個(gè)題目描述說得太繞了。關(guān)于游程編碼的概念，可以從網(wǎng)上找到介紹。

我先從示例入手簡(jiǎn)單講解一下題目：

首先我們要知道關(guān)于初始化的數(shù)組其實(shí)是經(jīng)過游程編碼處理后的數(shù)組，即壓縮后的數(shù)組。先展示游程編碼前后的數(shù)組：

編碼后
[3,8,0,9,2,5]

編碼前
[8,8,8,5,5] 

根據(jù)題目的介紹，對(duì)編碼后的數(shù)組進(jìn)行處理后：[(3,8),(0,9),(2,5)]。每個(gè)括號(hào)內(nèi)的其實(shí)就是(數(shù)字出現(xiàn)次數(shù),對(duì)應(yīng)的數(shù)字).也就是題目中所說的:

對(duì)于所有偶數(shù) i，A[i] 告訴我們?cè)谛蛄兄兄貜?fù)非負(fù)整數(shù)值 A[i + 1] 的次數(shù)。

然后我們可以嘗試進(jìn)行解碼：

解碼(3,8)得到數(shù)組[8,8,8]

解碼(0,9),由于次數(shù)為0，所以結(jié)果為[]

解碼(2,5)得到[5,5]

然后按照順序拼接起來[8,8,8,5,5]

而題目其實(shí)是要求我們根據(jù)輸入的編碼后的數(shù)組遍歷解碼(編碼前)的數(shù)組

/**
 * RLE 迭代器
 * @author RJH
 * create at 2018/9/9
 */
public class RLEIterator {
    /**
     * 當(dāng)前原數(shù)據(jù)的索引，可以看做是一個(gè)指向當(dāng)前訪問位置的指針
     */
    private int index=0;
    /**
     * 當(dāng)前遍歷的元素，對(duì)應(yīng)index+1的原數(shù)據(jù)的元素。其實(shí)是對(duì)應(yīng)游程編碼解壓后的元素
     */
    private int element=-1;
    /**
     * 初始化的原數(shù)據(jù)，其實(shí)是游程編碼壓縮后的數(shù)組
     */
    private int[] data;

    public RLEIterator(int[] A) {
        data=A;
    }

    public int next(int n) {
        while (n>0){
            if(index>data.length-2){
                element=-1;
                break;
            }
            //當(dāng)前元素出現(xiàn)次數(shù)
            int times=data[index];
            if(times>0){
                if(times>n){
                    data[index]=times-n;
                    element=data[index+1];
                }else{
                    //代表對(duì)應(yīng)的元素已經(jīng)遍歷完了，所以設(shè)為0
                    data[index]=0;
                    //當(dāng)前的元素則為index+1的元素
                    element=data[index+1];
                    index+=2;
                }
                n-=times;
            }else{
                //次數(shù)為0，直接訪問下一個(gè)偶數(shù)index對(duì)應(yīng)的次數(shù)
                index+=2;
            }
        }
        return element;
    }
}