Zigzag Iterator - Iterator xen kẽ hai mảng 1D

Cho hai mảng 1D, cài đặt iterator trả về phần tử xen kẽ. Có phương thức next() và hasNext().

Ví dụ: v1=[1,2], v2=[3,4,5,6] → [1,3,2,4,5,6].

Giải thuật (Queue lưu trạng thái)

Khởi tạo queue chứa cặp (index, array_id) cho mỗi mảng không rỗng. next() lấy front, trả giá trị, tăng index, đẩy lại nếu chưa hết. hasNext() kiểm tra queue không rỗng.

Cài đặt 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) : v1(v1), v2(v2) {
        if (!v1.empty()) q.push({0, 0});
        if (!v2.empty()) q.push({0, 1});
    }

    int next() {
        auto [idx, id] = q.front(); q.pop();
        int ret = (id == 1) ? v2[idx] : v1[idx];
        idx++;
        if ((id == 1 && idx < v2.size()) || (id == 0 && idx < v1.size()))
            q.push({idx, id});
        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;
    // ... tiếp tục
    return 0;
}

Đầu vào

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

Đầu ra

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