# 问题 原题链接：[https://leetcode.com/problems/flatten-2d-vector/](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`时就应该寻找有无下一个元素，如果没有就直接标记到达末尾。 # 解决方法 ```cpp 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(); } }; ```