y*****e 发帖数: 712 | 1 L家最爱考的面试题之一就是nested integer了,
还爱考各种iterator的implementation
这题是把两个最爱合在一起了。。。。感觉很有可能出,但网上没找到满意的答案.
题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的
public interface Data {
// Does this Data hold a collection?
public boolean isCollection();
// Returns the collection contained by this Data, or null if it is a
single element
public Collection> getCollection();
// Returns the single element contained by this Data, or null if it is a
collection
public T getElement();
}
我的思路把iterator放在一个stack里,有点像Preorder traversal,如果是element就
存进一个暂时的variable store里,call next的时候就return这个,如果是
isCollection的话,就再push stack里。但我对什么时候pop有点糊涂,其实我很怕用
generic type写东西,特别抽象,只好自己脑补成一个list
下面是我的solution,还请大家给点建议
public class iterator_nestedmap{
private Stack>> stack;
private T store;
public iterator_nestedmap(Collection> collection){
stack = new Stack>>();
stack.push(collection.iterator());
}
public boolean hasNext(){
if(store != null){
return true;
}
while(!stack.isEmpty()){
Iterator> iter = stack.peek();
if(!iter.hasNext()){
stack.pop();
continue;
}
Data element = iter.next();
if(element.isCollection()){
Collection> col = element.getCollection();
stack.push(col.iterator());
}
else{
store = element.getElement();
return true;
}
}
return false;
}
public T next(){
T result = null;
if(hasNext() || store != null){
result = store;
store = null;
return result;
}
return null;
}
} | t*****3 发帖数: 112 | 2 我的做法是在constructor初始化的时候直接转为一个iterator,反正不能修改。另外
整个可以看成树,只有叶子节点有整数,所以用什么遍历其实都无所谓,最后都是中序
。 | l******9 发帖数: 26 | 3 I used the stack Stack>
http://ideone.com/CIl8uy | q*c 发帖数: 9453 | 4 stack 不是更简单?每次看顶,单个就 pop, 多个就展开反着 push, 继续循环
处理第一个直到碰见单个。
【在 l******9 的大作中提到】 : I used the stack Stack> : http://ideone.com/CIl8uy
|
|