C++-এ Zigzag Iterator: দুটি অ্যারের এলিমেন্ট বiegos করে ইটারেটর বানানো

উদাহরণ

ইনপুট: v1 = [1,2], v2 = [3,4,5,6]

আউটপুট সিকোয়েন্স: [1,3,2,4,5,6]

সমাধানের পদ্ধতি (Queue of Pairs)

1. একটি কিউ q ঘোষণা করুন যা {index, array_id} পেয়ার রাখবে (array_id: 0 = v1, 1 = v2)।
2. কন্সট্রাক্টরে:
   • যদি v1 খালি না হয়, {0, 0} পুশ করুন।
   • যদি v2 খালি না হয়, {0, 1} পুশ করুন।
3. next():
   • কিউ থেকে ফ্রন্ট পেয়ার temp পপ করুন।
   • যদি temp.second == 1 (v2), তবে ret = v2[temp.first], ইনডেক্স বাড়ান, যদি বাকি থাকে তবে কিউতে পুশ করুন।
   • অন্যথায় (v1), ret = v1[temp.first], ইনডেক্স বাড়ান, বাকি থাকলে কিউতে পুশ করুন।
   • ret রিটার্ন করুন।
4. hasNext(): কিউ খালি নয় কিনা চেক করে রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class ZigzagIterator {
public:
    queue<pair<int, int>> q;
    vector<int> v1, v2;
    
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        this->v1 = v1;
        this->v2 = v2;
        if (v1.size()) q.push({0, 0});
        if (v2.size()) q.push({0, 1});
    }
    
    int next() {
        pair<int, int> temp = q.front(); q.pop();
        int ret = 0;
        if (temp.second == 1) {
            ret = v2[temp.first];
            temp.first++;
            if (temp.first < v2.size()) q.push(temp);
        } else {
            ret = v1[temp.first];
            temp.first++;
            if (temp.first < v1.size()) q.push(temp);
        }
        return ret;
    }
    
    bool hasNext() {
        return !q.empty();
    }
};

int main() {
    vector<int> v1 = {1,3,5,7}, v2 = {2,4,6,8,10,12,17};
    ZigzagIterator ob(v1, v2);
    cout << (ob.next()) << endl;  // 1
    cout << (ob.next()) << endl;  // 2
    cout << (ob.hasNext() ? "True" : "False") << endl; // True
    cout << (ob.next()) << endl;  // 3
    cout << (ob.next()) << endl;  // 4
    cout << (ob.next()) << endl;  // 5
    cout << (ob.hasNext() ? "True" : "False") << endl; // True
    cout << (ob.next()) << endl;  // 6
    cout << (ob.next()) << endl;  // 7
    cout << (ob.next()) << endl;  // 8
    cout << (ob.next()) << endl;  // 10
    cout << (ob.hasNext() ? "True" : "False") << endl; // True
    cout << (ob.next()) << endl;  // 12
    cout << (ob.next()) << endl;  // 17
    cout << (ob.hasNext() ? "True" : "False") << endl; // False
    return 0;
}

ইনপুট

{1,3,5,7},{2,4,6,8,10,12,17}

আউটপুট

1 2 True 3 4 5 True 6 7 8 10 True 12 17 False