281. 锯齿迭代器
给出两个一维的向量，请你实现一个迭代器，交替返回它们中间的元素。
示例:
输入: v1 = [1,2] v2 = [3,4,5,6] 输出:[1,3,2,4,5,6] 解析:通过连续调用 next 函数直到 hasNext 函数返回false，next 函数返回值的次序应依次为:[1,3,2,4,5,6]。
拓展：假如给你 k 个一维向量呢？你的代码在这种情况下的扩展性又会如何呢?
拓展声明：
“锯齿” 顺序对于 k > 2 的情况定义可能会有些歧义。所以，假如你觉得 “锯齿” 这个表述不妥，也可以认为这是一种 “循环”。例如：
输入:
[1,2,3]
[4,5,6,7]
[8,9]
输出: [1,4,8,2,5,9,3,6,7].
原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 4.9 MB, 提交时间: 2023-10-16 23:14:23
type ZigzagIterator struct {
nums []int
}
func Constructor(v1, v2 []int) *ZigzagIterator {
n1,n2:=len(v1),len(v2)
n:=n1
if n1<n2{
n=n2
}
nums :=[]int{}
for i:=0;i<n;i++{
if i<n1{
nums =append(nums,v1[i])
}
if i<n2{
nums =append(nums,v2[i])
}
}
return &ZigzagIterator{nums: nums}
}
func (this *ZigzagIterator) next() int {
if !this.hasNext(){
return 0
}
x:=this.nums[0]
this.nums = this.nums[1:]
return x
}
func (this *ZigzagIterator) hasNext() bool {
return len(this.nums)>0
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* obj := Constructor(param_1, param_2);
* for obj.hasNext() {
* ans = append(ans, obj.next())
* }
*/
python3 解法, 执行用时: 60 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-16 23:13:50
class ZigzagIterator:
def __init__(self, v1: List[int], v2: List[int]):
p = 0
self.arr = []
while p < len(v1) and p < len(v2):
self.arr.append(v1[p])
self.arr.append(v2[p])
p += 1
self.arr += v1[p:]
self.arr += v2[p:]
self.p = 0
def next(self) -> int:
self.p += 1
return self.arr[self.p - 1]
def hasNext(self) -> bool:
return self.p < len(self.arr)
# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())
java 解法, 执行用时: 2 ms, 内存消耗: 42.8 MB, 提交时间: 2023-10-16 23:13:05
public class ZigzagIterator {
Queue<Iterator<Integer>> queue = new LinkedList<>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
Iterator<Integer> it1 = v1.iterator();
Iterator<Integer> it2 = v2.iterator();
if (it1.hasNext()) {
queue.add(it1);
}
if (it2.hasNext()) {
queue.add(it2);
}
}
public int next() {
Iterator<Integer> it = queue.poll();
int v = it.next();
if (it.hasNext()) {
queue.add(it);
}
return v;
}
public boolean hasNext() {
if (!queue.isEmpty()) {
return true;
}
return false;
}
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/
cpp 解法, 执行用时: 4 ms, 内存消耗: 8.8 MB, 提交时间: 2023-10-16 23:12:30
class ZigzagIterator1 {
public:
ZigzagIterator1(vector<int>& v1, vector<int>& v2) {
int i = 0;
int j = 0;
while (i < v1.size() && j < v2.size()) {
nums.push_back(v1[i++]);
nums.push_back(v2[j++]);
}
while (i < v1.size()) {
nums.push_back(v1[i++]);
}
while (j < v2.size()) {
nums.push_back(v2[j++]);
}
}
int next() {
assert(hasNext());
return nums[index++];
}
bool hasNext() {
return index < nums.size();
}
private:
int index = 0;
vector<int> nums;
};
class ZigzagIterator2 {
public:
ZigzagIterator2(vector<int>& v1, vector<int>& v2) : nums1(v1), nums2(v2) {
}
int next() {
assert(hasNext());
if (i < nums1.size() && j < nums2.size()) {
if ((i + j) % 2 == 0) {
return nums1[i++];
} else {
return nums2[j++];
}
} else if (i < nums1.size()) {
return nums1[i++];
} else if (j < nums2.size()) {
return nums2[j++];
} else {
assert(false && "Unreachable!");
}
}
bool hasNext() {
return i < nums1.size() || j < nums2.size();
}
private:
int i = 0;
int j = 0;
vector<int> nums1;
vector<int> nums2;
};
class ZigzagIterator3 {
public:
ZigzagIterator3(vector<int>& v1, vector<int>& v2) {
i1 = v1.begin();
i2 = v2.begin();
e1 = v1.end();
e2 = v2.end();
}
int next() {
assert(hasNext());
int res;
if (i1 != e1 && i2 != e2) {
if (count % 2 == 0) {
res = *i1++;
} else {
res = *i2++;
}
count++;
return res;
}
if (i1 != e1) {
res = *i1++;
count++;
return res;
} else if (i2 != e2) {
res = *i2++;
count++;
return res;
} else {
assert(false && "No more next!");
}
}
bool hasNext() {
return i1 != e1 || i2 != e2;
}
private:
int i;
int j;
int count = 0;
vector<int>::iterator i1;
vector<int>::iterator i2;
vector<int>::iterator e1;
vector<int>::iterator e2;
};
class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
if (!v1.empty()) {
q.push(make_pair(v1.begin(), v1.end()));
}
if (!v2.empty()) {
q.push(make_pair(v2.begin(), v2.end()));
}
}
int next() {
assert(hasNext());
auto cur = q.front(); q.pop();
if (cur.first + 1 != cur.second) {
q.push(make_pair(cur.first + 1, cur.second));
}
return *cur.first;
}
bool hasNext() {
return !q.empty();
}
private:
queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
};
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i(v1, v2);
* while (i.hasNext()) cout << i.next();
*/