ধরুন আমাদের একটি পুনরাবৃত্তিকারী তৈরি করতে হবে যা একটি রান-লেংথ এনকোডেড সিকোয়েন্সের মাধ্যমে পুনরাবৃত্তি করে। এখানে ইটারেটরকে RLEIterator(int[] A) কল করে আরম্ভ করা হয়, যেখানে A হল একটি ক্রম-দৈর্ঘ্যের এনকোডিং। তাই আমরা বলতে পারি যে সকলের জন্য এমনকি i, A[i] আমাদেরকে বলে যে অ-ঋণাত্মক পূর্ণসংখ্যার মান A[i+1] ক্রমটিতে কতবার পুনরাবৃত্তি হয়েছে। এখানে পুনরাবৃত্তিকারী একটি ফাংশন সমর্থন করে −
-
next(int n):এই ফাংশনটি পরবর্তী n উপাদানগুলিকে (n>=1) নিঃশেষ করে দেয় এবং এইভাবে শেষ হওয়া শেষ উপাদানটি ফেরত দেয়। তাই যদি নিষ্কাশনের জন্য কোনো উপাদান অবশিষ্ট না থাকে, তার পরিবর্তে পরবর্তী রিটার্ন -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
-
পরবর্তী() পদ্ধতিতে ইনপুট হিসেবে n লাগে। এটি নিম্নরূপ কাজ করবে
-
যখন সূচক A[সূচক]
-
n :=n – A[সূচী], এবং সূচক বাড়ান 2
-
-
যদি ইনডেক্স> অ্যারের আকার A, তাহলে -1 ফেরত দিন
-
A[সূচি] :=A[সূচী] – n
-
A[index + 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
