LC: 281. Zigzag Iterator
https://leetcode.com/problems/zigzag-iterator/
Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator class:
ZigzagIterator(List<int> v1, List<int> v2)initializes the object with the two vectorsv1andv2.boolean hasNext()returnstrueif the iterator still has elements, andfalseotherwise.int next()returns the current element of the iterator and moves the iterator to the next element.
Example 1:
Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].Example 2:
Input: v1 = [1], v2 = []
Output: [1]Example 3:
Input: v1 = [], v2 = [1]
Output: [1]Constraints:
0 <= v1.length, v2.length <= 10001 <= v1.length + v2.length <= 2000-231 <= v1[i], v2[i] <= 231 - 1
Follow up: What if you are given k vectors? How well can your code be extended to such cases?
Clarification for the follow-up question:
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic".
Example:
The Essence:
Es wird eine Datenstruktur benötigt, die zwei Zeiger für die aktuelle Liste und den aktuellen Index hat. Die Queries next und hasNext müssen effizient abgearbeitet werden. Wenn die aktuellen Liste nicht so viele Elemente wie vom Index gezeigt hat, dann muss diese Liste für die nächste Liste übersprungen werden.
Details:
The list and index pointers can just be integers, with the list pointer going back and forth between 0 and 1. The index pointer should increase when an element is returned, or when hasNext is called.
For the follow-up problem of extending the algorithm to multiple list, one can use queue for prioritizing the lists or keep which sets are exhausted in an array or a set.
Default Code:
Last updated