LeetCode 251：展开二维向量

题目

Implement an iterator to flatten a 2d vector.

Example:

[1,2,3,4,5,6]
[1,2,3,4,5,6]
Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

题解：

用两个index 分别记录list 的 index 和当前 list的element index.

Time Complexity: Vector2D() O(1). hasNext() O(vec2d.size()). next() O(1). Space: O(1).

嵌套list解法：

1，提取 Vector2D(List> vec2d)  的参数为全局参数

2,抽出2个list的对应的index,如List.get(listIdx).get(elemIdx++)

int listIdx;代表外层list的索引
int elemIdx;代表内层list的索引

public class Vector2D {
    List> listOfList;
    int listIdx;
    int elemIdx;
 
    public Vector2D(List> vec2d) {
        listOfList = vec2d;
        listIdx = 0;
        elemIdx = 0;
    }
 
    public int next() {
        return listOfList.get(listIdx).get(elemIdx++);
    }
 
    public boolean hasNext() {
        while (listIdx < listOfList.size()) {
            if (elemIdx < listOfList.get(listIdx).size()) {
                return true;
            } else {
                listIdx++;
                elemIdx = 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();
 */

 借助Iterator迭代器解法

1，对外层list，取迭代器 Iterator> out;

2，对内层list，抽取迭代器 Iterator inner;

借助迭代器的原有方法，进行对齐使用！

public class Vector2D implements Iterator {
    Iterator> out;
    Iterator inner;
 
    public Vector2D(List> vec2d) {
        out = vec2d.iterator();
    }
 
    @Override
    public Integer next() {
        return inner.next();
    }
 
    @Override
    public boolean hasNext() {
        while ((inner == null || !inner.hasNext()) && out.hasNext()) {
            inner = out.next().iterator();
        }
 
        return inner != null && inner.hasNext();
    }
}

 相关leetcode

284. 顶端迭代器

341. 扁平化嵌套列表迭代器

173. 二叉搜索树迭代器