C++のRLEイテレータ

ランレングスでエンコードされたシーケンスを反復処理するイテレータを作成する必要があるとします。ここで、イテレータはRLEIterator（int [] A）を呼び出すことによって初期化されます。ここで、Aはシーケンスのランレングスエンコーディングです。したがって、すべてのiについて、A[i]は非負の整数値A[i+1]がシーケンス内で繰り返される回数を示していると言えます。ここで、イテレータは1つの関数をサポートします-

• next（int n）：この関数は、次のn個の要素（n> =1）を使い果たし、この方法で使い果たされた最後の要素を返します。したがって、使い尽くす要素が残っていない場合、nextは代わりに-1を返します。

A =[3,8,0,9,2,5]で開始するとします。これは、シーケンス[8,8,8,5,5]のランレングスエンコーディングです。これは、シーケンスが「スリーエイト、ゼロナイン、ツーファイブ」として読み取れるために行われます。したがって、Aで初期化した後、next（2）、next（1）、next（1）、next（2）を呼び出すと、最終結果は[8、8、5、-1]になります。

これを解決するには、次の手順に従います-

• イニシャライザで、配列をAとして初期化し、インデックス：=0

  を設定します。

• next（）メソッドでは、nを入力として受け取ります。これは次のように機能します

• 一方、インデックスA[インデックス]

  • n：=n – A [インデックス]、インデックスを2増やします

• インデックス>配列Aのサイズの場合、-1を返します

• A [インデックス]：=A[インデックス]– n

• A[インデックス+1]を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class RLEIterator {
   public:
   vector <int> A;
   int idx = 0;
   RLEIterator(vector<int>& A) {
      this->A = A;
      idx = 0;
   }
   int next(int n) {
      while(idx < A.size() && n > A[idx]){
         n -= A[idx];
         idx += 2;
      }
      if(idx >= A.size()) return -1;
      A[idx] = A[idx] - n;
      return A[idx + 1];
   }
};
main(){
   vector<int> v = {3,8,0,9,2,5};
   RLEIterator ob(v);
   cout << (ob.next(2)) << endl;
   cout << (ob.next(1)) << endl;
   cout << (ob.next(1)) << endl;
   cout << (ob.next(2)) << endl;
}

入力

Initialize with [3,8,0,9,2,5] and call next(2), next(1), next(1), next(2)

出力

8
8
5
-1