首页 > 代码库 > Flatten Nested List Iterator
Flatten Nested List Iterator
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example
Given the list
[[1,1],2,[1,1]]
, By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:[1,1,2,1,1]
.Given the list
[1,[4,[6]]]
, By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:[1,4,6]
.
Runtime: 626ms
1 /** 2 * // This is the interface that allows for creating nested lists. 3 * // You should not implement it, or speculate about its implementation 4 * class NestedInteger { 5 * public: 6 * // Return true if this NestedInteger holds a single integer, 7 * // rather than a nested list. 8 * bool isInteger() const; 9 *10 * // Return the single integer that this NestedInteger holds,11 * // if it holds a single integer12 * // The result is undefined if this NestedInteger holds a nested list13 * int getInteger() const;14 *15 * // Return the nested list that this NestedInteger holds,16 * // if it holds a nested list17 * // The result is undefined if this NestedInteger holds a single integer18 * const vector<NestedInteger> &getList() const;19 * };20 */21 class NestedIterator {22 public:23 NestedIterator(vector<NestedInteger> &nestedList) {24 // Initialize your data structure here.25 flatten(nestedList, result);26 index = 0;27 }28 29 // @return {int} the next element in the iteration30 int next() {31 // Write your code here32 return result[index++];33 }34 35 // @return {boolean} true if the iteration has more element or false36 bool hasNext() {37 // Write your code here38 return index < result.size();39 }40 41 private:42 vector<int> result;43 int index;44 45 void flatten(vector<NestedInteger> nestedList, vector<int>& result) {46 for (int i = 0; i < nestedList.size(); i++) {47 if (nestedList[i].isInteger())48 result.push_back(nestedList[i].getInteger());49 else 50 flatten(nestedList[i].getList(), result);51 }52 }53 };54 55 /**56 * Your NestedIterator object will be instantiated and called as such:57 * NestedIterator i(nestedList);58 * while (i.hasNext()) v.push_back(i.next());59 */
Flatten Nested List Iterator
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。