题目地址：https://leetcode-cn.com/problems/zigzag-iterator/
题目描述
Given two 1d vectors, implement an iterator to return their elements alternately.
Example:
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].
Follow up: What if you are given k 1d 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". For example:
Input:
[1,2,3]
[4,5,6,7]
[8,9]
Output: [1,4,8,2,5,9,3,6,7].
题目大意
给出两个一维的向量，请你实现一个迭代器，交替返回它们中间的元素。
解题方法
deque
看出题目的含义，有点类似于我们从不同链表中依次读取头部并删除头部的操作。所以可以使用数据结构来模拟这个操作，因此我们需要一个比较高效的能从头部删除元素的数据结构，比如双端队列deque。
具体做法是使用变量cur标识应该读取哪个deque，然后读取并删除该deque的头部，再修改变量cur。
C++代码如下：
class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
d1 = deque<int>(v1.begin(), v1.end());
d2 = deque<int>(v2.begin(), v2.end());
if (v1.empty())
cur = 1;
else
cur = 0;
}
int next() {
int val = 0;
if (cur == 0) {
val = d1.front(); d1.pop_front();
if (!d2.empty())
cur = 1;
} else if (cur == 1) {
val = d2.front(); d2.pop_front();
if (!d1.empty())
cur = 0;
}
return val;
}
bool hasNext() {
return !d1.empty() || !d2.empty();
}
private:
deque<int> d1, d2;
int cur = 0;
};
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i(v1, v2);
* while (i.hasNext()) cout << i.next();
*/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发