题目：
Implement an iterator to flatten a 2d vector.
For example,
Given 2d vector =
[
[1,2],
[3],
[4,5,6]
]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].
Hint:
- How many variables do you need to keep track?
- Two variables is all you need. Try with
xandy. - Beware of empty rows. It could be the first few rows.
- To write correct code, think about the invariant to maintain. What is it?
- The invariant is
xandymust always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it? - Not sure? Think about how you would implement
hasNext(). Which is more complex? - Common logic in two different places should be refactored into a common method.
Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.
链接： http://leetcode.com/problems/flatten-2d-vector/
题解：
构造一个2D的iterator。不太理解iterator的原理，第一想法是把vec2d里面的元素都读到Queue里 ，然后再逐个读取。这样的话初始化需要O(n)， next和hasNext都为O(1)，Space Complexity也是O(n)，虽然能ac，但是当vec2d足够大的时候会出问题。
Time Complexity - constructor - O(n)， hasNext - O(1)， next() - O(1)， Space Complexity - O(n)。
public class Vector2D {
private Queue<Integer> vec1d;
public Vector2D(List<List<Integer>> vec2d) {
vec1d = new LinkedList<>();
for(List<Integer> list : vec2d) {
for(int i : list) {
vec1d.offer(i);
}
}
}
public int next() {
if(hasNext())
return vec1d.poll();
else
return Integer.MAX_VALUE;
}
public boolean hasNext() {
return vec1d.size() > 0;
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Update: 保存两个变量来遍历vec2d
public class Vector2D {
private List<List<Integer>> list;
private int listIndex;
private int elemIndex;
public Vector2D(List<List<Integer>> vec2d) {
list = vec2d;
listIndex = 0;
elemIndex = 0;
}
public int next() {
return list.get(listIndex).get(elemIndex++);
}
public boolean hasNext() {
while(listIndex < list.size()) {
if(elemIndex < list.get(listIndex).size()) {
return true;
} else {
listIndex++;
elemIndex = 0;
}
}
return false;
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
二刷:
使用了ArrayList的iterator，这个算不算作弊...思路就是，一开始把vec2d里面每个list的iterator都加入到一个iters的ArrayList里。之后就可以很简单地写好hasNext()和next()两个方法了。
Java:
public class Vector2D implements Iterator<Integer> {
private List<Iterator<Integer>> iters;
private int curLine = 0;
public Vector2D(List<List<Integer>> vec2d) {
this.iters = new ArrayList<>();
for (List<Integer> list : vec2d) {
iters.add(list.iterator());
}
}
@Override
public Integer next() {
return iters.get(curLine).next();
}
@Override
public boolean hasNext() {
while (curLine < iters.size()) {
if (iters.get(curLine).hasNext()) return true;
else curLine++;
}
return false;
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Update:
还是使用两个元素来遍历
public class Vector2D implements Iterator<Integer> {
private List<List<Integer>> list;
private int curLine = 0;
private int curElem = 0;
public Vector2D(List<List<Integer>> vec2d) {
this.list = vec2d;
}
@Override
public Integer next() {
return list.get(curLine).get(curElem++);
}
@Override
public boolean hasNext() {
while (curLine < list.size()) {
if (curElem < list.get(curLine).size()) {
return true;
} else {
curLine++;
curElem = 0;
}
}
return false;
}
}
/**
* Your Vector2D object will be instantiated and called as such:
* Vector2D i = new Vector2D(vec2d);
* while (i.hasNext()) v[f()] = i.next();
*/
Reference:
http://web.cse.ohio-state.edu/software/2231/web-sw2/extras/slides/17a.Iterators.pdf
http://docs.oracle.com/javase/7/docs/api/
http://*.com/questions/21988341/how-to-iterate-through-two-dimensional-arraylist-using-iterator
http://www.cs.cornell.edu/courses/cs211/2005fa/Lectures/L15-Iterators%20&%20Inner%20Classes/L15cs211fa05.pdf
https://leetcode.com/discuss/50292/7-9-lines-added-java-and-c-o-1-space
https://leetcode.com/discuss/55199/pure-iterator-solution-additional-data-structure-list-get
https://leetcode.com/discuss/57984/simple-and-short-java-solution-with-iterator
https://leetcode.com/discuss/50356/my-concise-java-solution
https://leetcode.com/discuss/68860/java-o-1-space-solution
https://leetcode.com/discuss/71002/java-solution-beats-60-10%25