सी++ में आरएलई इटरेटर

मान लीजिए कि हमें एक इटरेटर बनाना है जो एक रन-लेंथ एन्कोडेड अनुक्रम के माध्यम से पुनरावृत्त हो। यहां इटरेटर को RLEIterator (int [] A) को कॉल करके प्रारंभ किया गया है, जहां ए अनुक्रम की रन-लम्बाई एन्कोडिंग है। तो हम कह सकते हैं कि सभी के लिए भी, ए[i] हमें बताता है कि अनुक्रम में गैर-ऋणात्मक पूर्णांक मान A[i+1] कितनी बार दोहराया जाता है। यहां इटरेटर एक फ़ंक्शन का समर्थन करता है -

• अगला (int n):यह फ़ंक्शन अगले n तत्वों (n> =1) को समाप्त कर देता है और इस तरह से समाप्त हो गया अंतिम तत्व लौटाता है। इसलिए यदि निकास के लिए कोई तत्व नहीं बचा है, तो इसके बजाय अगला -1 लौटाता है।

मान लीजिए कि हम ए =[3,8,0,9,2,5] से शुरू करते हैं, जो अनुक्रम [8,8,8,5,5] का एक रन-लेंथ एन्कोडिंग है। यह किया जाता है क्योंकि अनुक्रम को "तीन आठ, शून्य नौ, दो पांच" के रूप में पढ़ा जा सकता है। तो उन्हें ए के साथ शुरू करने के बाद, अगर हम अगला (2), अगला (1), अगला (1), अगला (2) कहते हैं, तो अंतिम परिणाम [8, 8, 5, -1] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• इनिशियलाइज़र में, एरे को ए के रूप में इनिशियलाइज़ करें, और इंडेक्स सेट करें:=0

• अगली () विधि में यह इनपुट के रूप में n लेता है। यह इस प्रकार काम करेगा

• जबकि इंडेक्स <ए और एन का आकार> ए [इंडेक्स]

  • n :=n - A[index], और इंडेक्स को 2 से बढ़ाएं

• यदि अनुक्रमणिका> सरणी A का आकार है, तो -1 लौटाएं

• ए [इंडेक्स]:=ए [इंडेक्स] - एन

• वापसी ए[इंडेक्स + 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