摘要：首先，根據迭代器需要不斷返回下一個元素，確定用堆棧來做。堆棧初始化數據結構，要先從后向前向堆棧壓入中的元素。在調用之前，先要用判斷下一個是還是，并進行的操作對要展開并順序壓入對直接返回。
Problem
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.
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].
Note
這個迭代器要實現三個功能：
初始化結構，找下一個元素，判斷是否存在下一個元素。
首先，根據迭代器需要不斷返回下一個元素，確定用堆棧來做。
堆棧初始化數據結構，要先從后向前向堆棧壓入nestedList中的元素。
在調用next()之前，先要用hasNext()判斷下一個NestedInteger是Integer還是List，并進行flatten的操作：對List要展開并順序壓入stack；對Integer直接返回true。這樣一來，調用next()的時候，返回的就一定是Integer了。
Solution
import java.util.Iterator;
public class NestedIterator implements Iterator {
Stack stack = new Stack();
public NestedIterator(List nestedList) {
for (int i = nestedList.size()-1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger cur = stack.peek();
if (cur.isInteger()) return true;
stack.pop();
for (int i = cur.getList().size()-1; i >= 0; i--) stack.push(cur.getList().get(i));
}
return false;
}
}
By using internalNext()
public class NestedIterator implements Iterator {
private NestedInteger peek = null;
private Iterator iterator;
private Stack> stack = new Stack();
public NestedIterator(List nestedList) {
iterator = nestedList.iterator();
peek = internalNext();
}
private NestedInteger internalNext() {
if (iterator.hasNext()) {
NestedInteger i = iterator.next();
if (i.isInteger()) return i;
else {
stack.add(iterator);
iterator = i.getList().iterator();
return internalNext();
}
} else if (stack.size() > 0) {
iterator = stack.pop();
return internalNext();
} else return null;
}
@Override
public Integer next() {
Integer next = peek.getInteger();
peek = internalNext();
return next;
}
@Override
public boolean hasNext() {
return peek != null;
}
}
A much much better method
public class NestedIterator implements Iterator {
private List flatList;
private int index;
public NestedIterator(List nestedList) {
flatList = new ArrayList<>();
flatten(nestedList);
}
public void flatten(List nestedList) {
for (NestedInteger i: nestedList) {
if (i.isInteger()) flatList.add(i.getInteger());
else flatten(i.getList());
}
}
@Override
public Integer next() {
return hasNext ? flatList.get(index++) : null;
}
@Override
public boolean hasNext() {
return index < flatList.size();
}
}
update 2018-11
public class NestedIterator implements Iterator {
Deque stack;
public NestedIterator(List nestedList) {
stack = new ArrayDeque<>();
for (int i = nestedList.size()-1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
if (hasNext()) {
return stack.pop().getInteger();
}
return null;
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger cur = stack.peek();
if (cur.isInteger()) return true;
else {
stack.pop();
List list = cur.getList();
for (int i = list.size()-1; i >= 0; i--) {
stack.push(list.get(i));
}
}
}
return false;
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65990.html
