摘要：首先，根據(jù)迭代器需要不斷返回下一個(gè)元素，確定用堆棧來(lái)做。堆棧初始化數(shù)據(jù)結(jié)構(gòu)，要先從后向前向堆棧壓入中的元素。在調(diào)用之前，先要用判斷下一個(gè)是還是，并進(jìn)行的操作對(duì)要展開并順序壓入對(duì)直接返回。
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
這個(gè)迭代器要實(shí)現(xiàn)三個(gè)功能：
初始化結(jié)構(gòu)，找下一個(gè)元素，判斷是否存在下一個(gè)元素。
首先，根據(jù)迭代器需要不斷返回下一個(gè)元素，確定用堆棧來(lái)做。
堆棧初始化數(shù)據(jù)結(jié)構(gòu)，要先從后向前向堆棧壓入nestedList中的元素。
在調(diào)用next()之前，先要用hasNext()判斷下一個(gè)NestedInteger是Integer還是List，并進(jìn)行flatten的操作：對(duì)List要展開并順序壓入stack；對(duì)Integer直接返回true。這樣一來(lái)，調(diào)用next()的時(shí)候，返回的就一定是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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65990.html
