小弟求问LinkedIn那道Deep Iterator的题# JobHunting - 待字闺中
l*h
1 楼
LinkedIn 的题
"Program an iterator for a List which may include nodes or List i.e. * {0,
{1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
前一阵一直不会写的Deep Iterator有点像
大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
已经遍历到最后用完了，就直接扔出stack
底下是程序
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
*
* {0,{1,2}, 3 ,{4,{5, 6}}}
*
* 0 - 1 - 2 - 3 - 4 - 5 - 6
*
*/
class DeepIterator implements Iterator {
private Stack stack;
public DeepIterator(ArrayList finalLists){
stack = new Stack();
stack.push(finalLists.iterator());
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
} else {
Iterator iterator = stack.peek();
if (!iterator.hasNext()) {
stack.pop();
return hasNext();
} else {
return true;
}
}
}
public Object next() {
if (hasNext()) {
Iterator iterator = stack.peek();
Object object = iterator.next();
if (object instanceof ArrayList) {
stack.push(((ArrayList) object).iterator());
return next();
} else {
return object;
}
}
return null;
}
public void remove() {
}
}
//下面是输出的例子
public class Question {
public Iterator getIterator(ArrayList lists) {
return new DeepIterator(lists);
}
public static void main(String[] args) {
ArrayList finalLists = new ArrayList();
finalLists.add(0);
ArrayList firstLevelList = new ArrayList();
firstLevelList.add(1);
firstLevelList.add(2);
finalLists.add(firstLevelList);
finalLists.add(3);
firstLevelList = new ArrayList();
firstLevelList.add(4);
ArrayList secondLevelList = new ArrayList();
secondLevelList.add(5);
secondLevelList.add(6);
firstLevelList.add(secondLevelList);
finalLists.add(firstLevelList);
System.out.print("The original Lists is --- > " + finalLists);
Question sol = new Question();
Iterator iterator = sol.getIterator(finalLists);
System.out.println();
System.out.print("The flatten Lists is --- > ");
while(iterator.hasNext()) {
System.out.print(iterator.next() + " --> ");
}
}
}
程序能出来，有个疑问，因为Integer 和 ArrayList 类型不同 所以只能用Object 代
替，ArrayList也没控制类型，Eclipse里面一片黄，真正面过这个题的是不是像
Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem
实现这个interface, 这样就解决类型的问题了？
"Program an iterator for a List which may include nodes or List i.e. * {0,
{1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
前一阵一直不会写的Deep Iterator有点像
大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
已经遍历到最后用完了，就直接扔出stack
底下是程序
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
*
* {0,{1,2}, 3 ,{4,{5, 6}}}
*
* 0 - 1 - 2 - 3 - 4 - 5 - 6
*
*/
class DeepIterator implements Iterator {
private Stack
public DeepIterator(ArrayList finalLists){
stack = new Stack
stack.push(finalLists.iterator());
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
} else {
Iterator iterator = stack.peek();
if (!iterator.hasNext()) {
stack.pop();
return hasNext();
} else {
return true;
}
}
}
public Object next() {
if (hasNext()) {
Iterator iterator = stack.peek();
Object object = iterator.next();
if (object instanceof ArrayList) {
stack.push(((ArrayList) object).iterator());
return next();
} else {
return object;
}
}
return null;
}
public void remove() {
}
}
//下面是输出的例子
public class Question {
public Iterator getIterator(ArrayList lists) {
return new DeepIterator(lists);
}
public static void main(String[] args) {
ArrayList finalLists = new ArrayList();
finalLists.add(0);
ArrayList firstLevelList = new ArrayList();
firstLevelList.add(1);
firstLevelList.add(2);
finalLists.add(firstLevelList);
finalLists.add(3);
firstLevelList = new ArrayList();
firstLevelList.add(4);
ArrayList secondLevelList = new ArrayList();
secondLevelList.add(5);
secondLevelList.add(6);
firstLevelList.add(secondLevelList);
finalLists.add(firstLevelList);
System.out.print("The original Lists is --- > " + finalLists);
Question sol = new Question();
Iterator iterator = sol.getIterator(finalLists);
System.out.println();
System.out.print("The flatten Lists is --- > ");
while(iterator.hasNext()) {
System.out.print(iterator.next() + " --> ");
}
}
}
程序能出来，有个疑问，因为Integer 和 ArrayList 类型不同 所以只能用Object 代
替，ArrayList也没控制类型，Eclipse里面一片黄，真正面过这个题的是不是像
Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem
实现这个interface, 这样就解决类型的问题了？
