251. Flatten 2D Vector

Problem:
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].
6/7/2018 update:
In hasNext(), inner != null controls the corner case [] or inner.hasNext() is used, so inner should not be null.
--------------------------------------------------------------------------------------------------------------------------------------------
4/12/2018 update:
We use while in hasNext() to cover the case like:[ [], [], [1,2,3] ]. We should return null if user calls next() directly without calling hasNext() first when there is nothing left. 
为什么要在hasNext里面准备inner iterator? 因为在判断hasNext()的时候,如果inner为空或者没有下一个,我们会去更新inner,这样自然而然就需要在hasNext准备下一个inner。
Analysis:
Use 2 iterators, 1 is on Integer level (j) the other is on List level (i). Once j reaches the end, then update j from i.next(). Code is as follows:


 public class Vector2D implements Iterator<Integer> {
    Iterator<Integer> inner;
    Iterator<List<Integer>> outer;
    public Vector2D(List<List<Integer>> vec2d) {
        outer = vec2d.iterator();
    }

    @Override
    public Integer next() {
        return hasNext() ? inner.next() : null;
    }

    @Override
    public boolean hasNext() {
        while ((inner == null || !inner.hasNext()) && outer.hasNext()) {
            inner = outer.next().iterator();
        }
        return inner != null && inner.hasNext();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */
Why update j inside hasNext()? Because if we dont do so, we would upate j in both next() and hasNext() methods.
Why do we use while instead of if when updating j?  Because when run with test case[[], [3]], if we use if, then the condition j != null && j.hasNext() will be false, but we still have [3] left.

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array