首页 > 代码库 > 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.
Notice You don‘t need to implement the remove method.
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]
.
题目中的NestedInteger应该是实际当中General Grouping Object (or Container)的特例。看到这种数据结构的第一反应就是用stack。注意倒叙插入即可。
1 /** 2 * // This is the interface that allows for creating nested lists. 3 * // You should not implement it, or speculate about its implementation 4 * public interface NestedInteger { 5 * 6 * // @return true if this NestedInteger holds a single integer, 7 * // rather than a nested list. 8 * public boolean isInteger(); 9 * 10 * // @return the single integer that this NestedInteger holds, 11 * // if it holds a single integer 12 * // Return null if this NestedInteger holds a nested list 13 * public Integer getInteger(); 14 * 15 * // @return the nested list that this NestedInteger holds, 16 * // if it holds a nested list 17 * // Return null if this NestedInteger holds a single integer 18 * public List<NestedInteger> getList(); 19 * } 20 */ 21 import java.util.Iterator; 22 23 public class NestedIterator implements Iterator<Integer> { 24 25 Stack<NestedInteger> stack; 26 public NestedIterator(List<NestedInteger> nestedList) { 27 // Initialize your data structure here. 28 stack = new Stack<NestedInteger>(); 29 if(nestedList!=null){ 30 for(int i=nestedList.size()-1;i>=0;i--){ 31 stack.push(nestedList.get(i)); 32 } 33 } 34 } 35 36 // @return {int} the next element in the iteration 37 @Override 38 public Integer next() { 39 // Write your code here 40 return stack.pop().getInteger(); 41 } 42 43 // @return {boolean} true if the iteration has more element or false 44 @Override 45 public boolean hasNext() { 46 // Write your code here 47 while(!stack.empty()){ 48 NestedInteger cur = stack.peek(); 49 if(cur.isInteger()) return true; 50 stack.pop(); 51 List<NestedInteger> list = cur.getList(); 52 if(list!=null){ 53 for(int i=list.size()-1;i>=0;i--){ 54 stack.push(list.get(i)); 55 } 56 } 57 } 58 return false; 59 } 60 61 @Override 62 public void remove() {} 63 } 64 65 /** 66 * Your NestedIterator object will be instantiated and called as such: 67 * NestedIterator i = new NestedIterator(nestedList); 68 * while (i.hasNext()) v.add(i.next()); 69 */
Flatten Nested List Iterator
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。