Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
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 - Update (2015-09-18):
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, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].
[分析] 三种实现方案,方案1针对原题,方案2和方案3针对扩展到k个输入链表的情况,其中方案3使用队列很巧妙, 方案2中hasNext()在仅剩一个链表时复杂度是O(k),而方案3始终是O(1)
public class ZigzagIterator {
private int active = 0;
private List<Iterator<Integer>> iters;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
iters = new ArrayList<Iterator<Integer>>();
iters.add(v1.iterator());
iters.add(v2.iterator());
}
public int next() {
active = 1 - active;
return iters.get(1 - active).next();
}
public boolean hasNext() {
if (iters.get(active).hasNext()) {
return true;
} else if (iters.get(1 - active).hasNext()) {
active = 1 - active;
return true;
} else {
return false;
}
}
}
// Method 2: 扩展至k,使用数组保存各链表的iterator
public class ZigzagIterator {
private int total = 2;
private int active = 0;
private List<Iterator<Integer>> iters;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
iters = new ArrayList<Iterator<Integer>>();
iters.add(v1.iterator());
iters.add(v2.iterator());
}
public int next() {
int curr = active;
active++;
if (active == total) active = 0;
return iters.get(curr).next();
}
public boolean hasNext() {
if (iters.get(active).hasNext()) {
return true;
} else {
for (int i = 1; i <= total; i++) {
int next = (active + i) % total;
if (iters.get(next).hasNext()) {
active = next;
return true;
}
}
return false;
}
}
}
// Method 3
public class ZigzagIterator {
private LinkedList<Iterator<Integer>> queue = new LinkedList<Iterator<Integer>>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
if (v1.size() > 0)
queue.offer(v1.iterator());
if (v2.size() > 0)
queue.offer(v2.iterator());
}
public int next() {
Iterator<Integer> active = queue.poll();
Integer result = active.next();
if (active.hasNext()) queue.offer(active);
return result;
}
public boolean hasNext() {
if (!queue.isEmpty()) return true;
else return false;
}
}
分享到:
相关推荐
实现Varint + ZigZag的编解码过程,里面有我自己对Vint编解码实现的算法 ,VInt编码为Varint编码和ZigZag编码的结合,为一种将64位二进制编码的有符号整型编码在最多10字节中的编码方式。Varint编码为一种将64位二...
ZIGZAG突破交易策略_V1_zigzag指标_Zigzag突破开仓策略_源码.rar.rar
zigzag算法的python版本,支持非正方形图像的zigzag列表生成,包含ZigZag()和deZigZag()函数,后者可实现原图重组。
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
ZIGZAG突破交易策略_V1_zigzag指标_Zigzag突破开仓策略_zigzag_zigzag突破_突破_源码.zip
自己编写zigzag算法的matlab实现
【达摩老生出品,必属精品,亲测校正,质量保证】 ...源码说明: matlab实现zigzag算法,将八成八的矩阵按zigzag化成向量,包含完整代码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
利用zigzag指标 和斐波那契序列 做单 mq4文件源码,可编译位ex4文件
用matlab实现zigzag,将八成八的矩阵按zigzag化成向量
自己写的8*8矩阵zigzag反扫描的代码
zigzag算法的matlab实现,很不错的东西
该程序实现了对一幅数字图像在像素级别上按照ZigZag方式扫描排列的功能
Unity曲折无限跑酷游戏源码Zigzag Infinite Unity曲折无限跑酷游戏源码Zigzag Infinite Unity曲折无限跑酷游戏源码Zigzag Infinite Unity曲折无限跑酷游戏源码Zigzag Infinite Unity曲折无限跑酷游戏源码Zigzag ...
对yuv视频文件进行zigzag编码和解码,并保存为.dat压缩文件并计算压缩比,解压后计算psnr值
利用verilog编码实现输入4*4矩阵块数据的zigzag扫描1*16数据输出,压缩包包括verilog代码以及testbench仿真代码,简单易行,亲测可用。
带有之字转向峰值价格标签的 Boa_ZigZag 指标。
zigzag图像处理
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Java AC版本
ZigZag Decoding: Combating Hidden Terminals in Wireless Networks