【MEDIUM】Flatten 2D Vector

发布于: 2019-02-02 21:51
阅读: 19
评论: 0
喜欢: 0

问题

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 x and y.
  • 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 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?
  • 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.

分析过程

  • 输入:一个二维数组,可能存在空行
  • 输出:一个展平后的一位数组
  • 思路:题目要求写的类似于一个迭代器。由于可能存在空行,所以hasNext方法不能简单地判断索引有没有到达最后。就算索引没有到达最后,如果后面全是空行,也算到结尾了。因此在next时就应该寻找有无下一个元素,如果没有就直接标记到达末尾。

解决方法

class Vector2D {
public:
    Vector2D(vector<vector<int>> data) {
        _data = data;
        _x = -1;
        _y = 0;
        _moveToNextNotNullItem();
    }
    
    // 使用 y = -1 标记已经到结尾
    bool hasNext() {
        return _y > -1;
    }
    
    int next() {
        int val = _data[_y][_x];
        _moveToNextNotNullItem();
        return val;
    }
    
private:
    vector<vector<int>> _data;
    int _x, _y;
    
    void _moveToNextNotNullItem() {
        // 标记是否到结尾了
        bool isReachEnd = _y >= _data.size();
        // 跳过空行
        while (!isReachEnd && _isCurrentEmptyRow()) {
            ++_y;
            _x = -1;
            isReachEnd = _y >= _data.size();
        }
        // 已达结尾
        if (isReachEnd) {
            // 标记,退出
            _y = -1;
            return;
        }
        // 已经跳过空行且没有到结尾
        if (_x < (int)(_data[_y].size() - 1)) {
            // 本行没有结束,x 后移
            ++_x;
        } else {
            // 本行已经结束,y 下移,递归
            ++_y;
            _x = -1;
            _moveToNextNotNullItem();
        }
    }
    
    bool _isCurrentEmptyRow() {
        if (_y <= -1) {
            return true;
        }
        return _data[_y].empty();
    }
};

int main() {
    vector<vector<int>> data = {
        {},
        {},
        {},
        {1,2},
        {3},
        {},
        {4,5,6}
    };
    Vector2D vector(data);
    
    while (vector.hasNext()) {
        cout << vector.next() << endl;
    }
    
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕