[LeetCode] 251. Flatten 2D Vector

[grandyang]

 

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:

1. How many variables do you need to keep track?
2. Two variables is all you need. Try with x and y.
3. Beware of empty rows. It could be the first few rows.
4. To write correct code, think about the invariant to maintain. What is it?
5. The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant  ahead of time  or  right when you need it?
6. Not sure? Think about how you would implement hasNext(). Which is more complex?
7. 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.

 

这道题让我们压平一个二维向量数组，并且实现一个 iterator 的功能，包括 next 和 hasNext 函数，那么最简单的方法就是将二维数组按顺序先存入到一个一维数组里，然后此时只要维护一个变量i来记录当前遍历到的位置，hasNext 函数看当前坐标是否小于元素总数，next 函数即为取出当前位置元素，坐标后移一位，参见代码如下：                      

 

解法一：

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d) {
        for (auto a : vec2d) {
            v.insert(v.end(), a.begin(), a.end());
        }    
    }
    int next() {
        return v[i++];
    }
    bool hasNext() {
        return i < v.size();
    }
private:
    vector<int> v;
    int i = 0;
};

 

下面我们来看另一种解法，不直接转换为一维数组，而是维护两个变量x和y，将x和y初始化为0，对于 hasNext 函数，检查当前x是否小于总行数，y是否和当前行的列数相同，如果相同，说明要转到下一行，则x自增1，y初始化为0，若此时x还是小于总行数，说明下一个值可以被取出来，那么在 next 函数就可以直接取出行为x，列为y的数字，并将y自增1，参见代码如下：

 

解法二：

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d): data(vec2d), x(0), y(0) {}

    int next() {
        hasNext();
        return data[x][y++];
    }
    bool hasNext() {
        while (x < data.size() && y == data[x].size()) {
            ++x; 
            y = 0;
        }
        return x < data.size();
    }    
private:
    vector<vector<int>> data;
    int x, y;
};

 

题目中的 Follow up 让我们用 interator 来做，C++中 iterator 不像 Java 中的那么强大，自己本身并没有包含 next 和 hasNext 函数，所以得自己来实现，将x定义为行的 iterator，再用个 end 指向二维数组的末尾，定义一个整型变量y来指向列位置，实现思路和上一种解法完全相同，只是写法略有不同，参见代码如下：

 

解法三：

class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec2d): x(vec2d.begin()), end(vec2d.end()) {}
    
    int next() {
        hasNext();
        return (*x)[y++];
    }
    bool hasNext() {
        while (x != end && y == (*x).size()) {
            ++x; 
            y = 0;
        }
        return x != end;
    }
private:
    vector<vector<int>>::iterator x, end;
    int y = 0;
};

 

Github 同步地址：

#251

 

类似题目：

Binary Search Tree Iterator

Zigzag Iterator

Peeking Iterator

Flatten Nested List Iterator

 

参考资料：

https://leetcode.com/problems/flatten-2d-vector/

https://leetcode.com/problems/flatten-2d-vector/discuss/67652/7-9-lines-added-Java-and-C%2B%2B-O(1)-space.

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[LukLau]

大佬 可以咨询下？ 用Java封装的迭代器有什么问题吗? 我在lintcode commit 失败

public class Vector2D implements Iterator<Integer> {

    private Iterator<List<Integer>> iterator;

    private Iterator<Integer> secondIterator;

    public Vector2D(List<List<Integer>> vec2d) {
        if (!vec2d.isEmpty()) {
            // Initialize your data structure here
            this.iterator = vec2d.iterator();
            this.secondIterator = this.iterator.next().iterator();
        }
    }

    @Override
    public Integer next() {
        if (iterator == null) {
            return null;
        }
        while (!secondIterator.hasNext()) {
            if (!iterator.hasNext()) {
                return null;
            }
            secondIterator = iterator.next().iterator();
            if (secondIterator.hasNext()) {
                return secondIterator.next();
            }
        }
        return secondIterator.next();
    }


    @Override
    public boolean hasNext() {
        if (iterator == null) {
            return false;
        }
        if (secondIterator.hasNext()) {
            return true;
        }
        if (!iterator.hasNext()) {
            return false;
        }
        secondIterator = iterator.next().iterator();

        return secondIterator.hasNext();
        // Write your code here
    }

    @Override
    public void remove() {
    }

    public static void main(String[] args) {
        Vector2D vector2D = new Vector2D(Arrays.asList(new ArrayList<>(), new ArrayList<>(), Arrays.asList(1, 2, 3), new ArrayList<>(), Arrays.asList(4)));
        System.out.println(vector2D.next());
        System.out.println(vector2D.next());
        System.out.println(vector2D.next());
        System.out.println(vector2D.next());
        System.out.println(vector2D.next());
        System.out.println(vector2D.next());


    }
}