ধরুন আমাদের একটি পুনরাবৃত্তিকারী তৈরি করতে হবে যা একটি রান-লেংথ এনকোডেড সিকোয়েন্সের মাধ্যমে পুনরাবৃত্তি করে। এখানে ইটারেটরকে 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