【MEDIUM】Flatten 2D Vector

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

问题

原题链接:https://leetcode.com/problems/flatten-2d-vector/

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext.

Example:

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // return 1
iterator.next(); // return 2
iterator.next(); // return 3
iterator.hasNext(); // return true
iterator.hasNext(); // return true
iterator.next(); // return 4
iterator.hasNext(); // return false

Notes:

  • Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases. Please see here for more details.
  • You may assume that next() call will always be valid, that is, there will be at least a next element in the 2d vector when next() is called.

分析过程

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

解决方法

class Vector2D {
public:
    Vector2D(vector<vector<int>> v) {
        _data = v;
        _x = -1;
        _y = 0;
        _moveToNextNotNullItem();
        
    }
    
    int next() {
        int val = _data[_y][_x];
        _moveToNextNotNullItem();
        return val;
    }
    
    bool hasNext() {
        return _y > -1;
    }
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();
    }
};

Thanks for reading.

All the best wishes for you! 💕