摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。
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;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/65990.html
