C++ में RLE इटरेटर (RLE Iterator)

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

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

समाधान दृष्टिकोण

1. इनिशियलाइज़र में: ऐरे A स्टोर करें, idx := 0

2. next(n) में: जब तक idx < A.size() और n > A[idx]: n -= A[idx], idx += 2

3. यदि idx ≥ A.size() तो -1 लौटाएं

4. A[idx] -= n, A[idx+1] लौटाएं

C++ कार्यान्वयन

#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]; 
    } 
}; 

int 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; 
    return 0; 
}

इनपुट

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

आउटपुट

8 8 5 -1