-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathZigzagIterator_281.java
More file actions
111 lines (94 loc) · 3.1 KB
/
Copy pathZigzagIterator_281.java
File metadata and controls
111 lines (94 loc) · 3.1 KB
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package com.leetcode.queue;
import com.algorithm.tree.segmentTree.IntervalSum;
import java.util.*;
/**
* Created by charles on 11/22/16.
* 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].
3 Solutions : http://likesky3.iteye.com/blog/2247236
As for K list followup, it is delicate to use Queue.
*/
public class ZigzagIterator_281 {
private LinkedList<Iterator<Integer>> queue = new LinkedList<>();
public ZigzagIterator_281(List<Integer> v1, List<Integer> v2, List<Integer> v3) {
if (v1.size() > 0) {
queue.offer(v1.iterator());
}
if (v2.size() > 0) {
queue.offer(v2.iterator());
}
if (v3.size() > 0) {
queue.offer(v3.iterator());
}
}
public int next() {
// poll one iterator from queue
// then get next integer
Iterator<Integer> active = queue.poll();
Integer res = active.next();
// after work, put iterator back to queue if hasnext
if (active.hasNext()) {
queue.offer(active);
}
return res;
}
public boolean hasNext() {
if (!queue.isEmpty()) {
return true;
}
return false;
}
public static void main(String[] args) {
List<Integer> v1 = Arrays.asList(1,2,3);
List<Integer> v2 = Arrays.asList(4,5,6,7);
List<Integer> v3 = Arrays.asList(8,9);
ZigzagIterator_281 zig = new ZigzagIterator_281(v1, v2, v3);
while (zig.hasNext()) {
System.out.print(zig.next() + ", ");
}
}
}
// for follow up, use array list to keep iterator of each list
class ZigzagIterator_solution2 {
private int total = 2;
private int active = 0;
private List<Iterator<Integer>> iters;
ZigzagIterator_solution2(List<Integer> v1, List<Integer> v2) {
iters = new ArrayList<>();
iters.add(v1.iterator());
iters.add(v2.iterator());
}
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;
}
}
}