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();
}
}
dev4future 