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

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

編寫一個遍歷游程編碼序列的迭代器。
迭代器由RLEIterator(int[] A)初始化，其中A是某個序列的游程編碼。更具體地，對于所有偶數(shù) i，A[i] 告訴我們在序列中重復(fù)非負整數(shù)值 A[i + 1] 的次數(shù)。
迭代器支持一個函數(shù)：next(int n)，它耗盡接下來的n個元素（n >= 1）并返回以這種方式耗去的最后一個元素。如果沒有剩余的元素可供耗盡，則 next返回-1。
例如，我們以A = [3,8,0,9,2,5]開始，這是序列 [8,8,8,5,5] 的游程編碼。這是因為該序列可以讀作 “三個零，零個九，兩個五”。
示例：
輸入：["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 個項，返回 8?，F(xiàn)在剩下的序列是 [8, 5, 5]。

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

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

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

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

我先從示例入手簡單講解一下題目：

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

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

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

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

對于所有偶數(shù) i，A[i] 告訴我們在序列中重復(fù)非負整數(shù)值 A[i + 1] 的次數(shù)。

然后我們可以嘗試進行解碼：

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

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

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

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

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

/**
 * RLE 迭代器
 * @author RJH
 * create at 2018/9/9
 */
public class RLEIterator {
    /**
     * 當(dāng)前原數(shù)據(jù)的索引，可以看做是一個指向當(dāng)前訪問位置的指針
     */
    private int index=0;
    /**
     * 當(dāng)前遍歷的元素，對應(yīng)index+1的原數(shù)據(jù)的元素。其實是對應(yīng)游程編碼解壓后的元素
     */
    private int element=-1;
    /**
     * 初始化的原數(shù)據(jù)，其實是游程編碼壓縮后的數(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{
                    //代表對應(yīng)的元素已經(jīng)遍歷完了，所以設(shè)為0
                    data[index]=0;
                    //當(dāng)前的元素則為index+1的元素
                    element=data[index+1];
                    index+=2;
                }
                n-=times;
            }else{
                //次數(shù)為0，直接訪問下一個偶數(shù)index對應(yīng)的次數(shù)
                index+=2;
            }
        }
        return element;
    }
}