281. Zigzag Iterator

using System.Collections.Generic;
public class ZigzagIterator {
    private List<List<int>> vectors = new List<List<int>>();
    private Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
    public ZigzagIterator(List<int> v1, List<int> v2) {
        vectors.Add(v1);
        vectors.Add(v2);
        for (int i = 0; i < vectors.Count; i++) {
            if (vectors[i].Count > 0) {
                queue.Enqueue(new KeyValuePair<int, int>(i, 0));
            }
        }
    }
    public int Next() {
        var pointer = queue.Dequeue();
        int vecIndex = pointer.Key;
        int elemIndex = pointer.Value;
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].Count) {
            queue.Enqueue(new KeyValuePair<int, int>(vecIndex, nextElemIndex));
        }
        return vectors[vecIndex][elemIndex];
    }
    public bool HasNext() {
        return queue.Count > 0;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ZigzagIterator {
    private List<List<int>> vectors = new List<List<int>>();
    private queue<KeyValuePair<int, int>> queue = new queue<KeyValuePair<int, int>>();
    public ZigzagIterator(List<int> v1, List<int> v2) {
        vectors.push_back(v1);
        vectors.push_back(v2);
        for (int i = 0; i < vectors.size(); i++) {
            if (vectors[i].size() > 0) {
                queue.Enqueue(new KeyValuePair<int, int>(i, 0));
            }
        }
    }
    public int Next() {
        var pointer = queue.Dequeue();
        int vecIndex = pointer.Key;
        int elemIndex = pointer.Value;
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].size()) {
            queue.Enqueue(new KeyValuePair<int, int>(vecIndex, nextElemIndex));
        }
        return vectors[vecIndex][elemIndex];
    }
    public bool HasNext() {
        return queue.size() > 0;
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import javafx.util.Pair;

public class ZigzagIterator {
    private List<List<Integer>> vectors = new ArrayList<>();
    private LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.vectors.add(v1);
        this.vectors.add(v2);
        int index = 0;
        for (List<Integer> vec : this.vectors) {
            if (vec.size() > 0)
                this.queue.add(new Pair<>(index, 0));
            index++;
        }
    }

    public int next() {
        Pair<Integer, Integer> pointer = this.queue.removeFirst();
        Integer vecIndex = pointer.getKey();
        Integer elemIndex = pointer.getValue();
        Integer nextElemIndex = elemIndex + 1;
        if (nextElemIndex < this.vectors.get(vecIndex).size())
            this.queue.addLast(new Pair<>(vecIndex, nextElemIndex));

        return this.vectors.get(vecIndex).get(elemIndex);
    }

    public boolean hasNext() {
        return !this.queue.isEmpty();
    }
}

class ZigzagIterator {
    constructor(v1, v2) {
        this.vectors = [v1, v2];
        this.queue = [];
        this.vectors.forEach((vec, index) => {
            if (vec.length > 0) {
                this.queue.push([index, 0]);
            }
        });
    }

    next() {
        const [vecIndex, elemIndex] = this.queue.shift();
        const nextElemIndex = elemIndex + 1;
        if (nextElemIndex < this.vectors[vecIndex].length) {
            this.queue.push([vecIndex, nextElemIndex]);
        }
        return this.vectors[vecIndex][elemIndex];
    }

    hasNext() {
        return this.queue.length > 0;
    }
}

from collections import deque

class ZigzagIterator:
    def __init__(self, v1, v2):
        self.vectors = [v1, v2]
        self.queue = deque((i, 0) for i, vec in enumerate(self.vectors) if vec)

    def next(self):
        vecIndex, elemIndex = self.queue.popleft()
        if elemIndex + 1 < len(self.vectors[vecIndex]):
            self.queue.append((vecIndex, elemIndex + 1))
        return self.vectors[vecIndex][elemIndex]

    def hasNext(self):
        return bool(self.queue)

type ZigzagIterator struct {
    vectors [][]int
    queue   []struct {
        vecIndex  int
        elemIndex int
    }
}

func Constructor(v1, v2 []int) ZigzagIterator {
    z := ZigzagIterator{
        vectors: [][]int{v1, v2},
    }
    for i, vec := range z.vectors {
        if len(vec) > 0 {
            z.queue = append(z.queue, struct {
                vecIndex  int
                elemIndex int
            }{i, 0})
        }
    }
    return z
}

func (z *ZigzagIterator) next() int {
    p := z.queue[0]
    z.queue = z.queue[1:]
    vecIndex, elemIndex := p.vecIndex, p.elemIndex
    nextElemIndex := elemIndex + 1
    if nextElemIndex < len(z.vectors[vecIndex]) {
        z.queue = append(z.queue, struct {
            vecIndex  int
            elemIndex int
        }{vecIndex, nextElemIndex})
    }
    return z.vectors[vecIndex][elemIndex]
}

func (z *ZigzagIterator) hasNext() bool {
    return len(z.queue) > 0
}

Algorithm

Инициализация объекта:

Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors.

Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс elementа в этом списке, если список не пуст.

Метод next:

Удалите первую пару индексов из очереди.

Извлеките element из соответствующего списка по указанным индексам.

Если в текущем списке есть еще elementы, добавьте новую пару индексов (тот же список, следующий element) в конец очереди.

return извлеченный element.

Метод hasNext:

Проверьте, пуста ли очередь.

return true, если в очереди есть elementы, и false в противном случае.

😎