Binary Search Tree Iterator
https://leetcode.com/problems/binary-search-tree-iterator/
public class BSTIterator { Stack<TreeNode> st=new Stack<TreeNode>(); TreeNode cur=null; public BSTIterator(TreeNode root) { cur=root; while(cur!=null){ st.push(cur); cur=cur.left; } } /** @return whether we have a next smallest number */ public boolean hasNext() { return !st.empty(); } /** @return the next smallest number */ public int next() { TreeNode tmp=st.pop(); cur=tmp; if (cur.right!=null){ cur=cur.right; while(cur!=null){ st.push(cur); cur=cur.left; } } return tmp.val; } } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */
Peeking Iterator
https://leetcode.com/problems/peeking-iterator/
// Java Iterator interface reference: // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html class PeekingIterator implements Iterator<Integer> { private Iterator<Integer> it; boolean flag=false; Integer nextElement=null; public PeekingIterator(Iterator<Integer> iterator) { // initialize any member here. this.it=iterator; } // Returns the next element in the iteration without advancing the iterator. public Integer peek() { if (!flag){ nextElement=it.next(); flag=true; } return nextElement; } // hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. @Override public Integer next() { if (flag){ flag=false; Integer res=nextElement; nextElement=null; return res; }else{ return it.next(); } } @Override public boolean hasNext() { return flag||it.hasNext(); } }
Zigzag Iterator
Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question – Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].
[思路]
iterator都放到一个list里, 用一个count循环,
public class zigZagIterator { private List<Iterator<Integer>> list=new ArrayList<Iterator<Integer>>(); int count=0; public zigZagIterator(Iterator<Integer> v1, Iterator<Integer> v2) { list.add(v1); list.add(v2); } public int next(){ int ret=list.get(count).next(); if (!list.get(count).hasNext()) list.remove(count); else count++; if (list.size()>0) count%=list.size(); return ret; } public boolean hasNext(){ return !list.isEmpty(); } }