My code:
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class NestedIterator implements Iterator<Integer> {
Stack<Iterator<NestedInteger>> st = new Stack<>();
NestedInteger next;
public NestedIterator(List<NestedInteger> nestedList) {
st.push(nestedList.iterator());
}
@Override
public Integer next() {
return next == null ? null : next.getInteger();
}
@Override
public boolean hasNext() {
while (!st.isEmpty()) {
if (!st.peek().hasNext()) {
st.pop();
}
else {
next = st.peek().next();
if (next.isInteger()) {
return true;
}
else {
st.push(next.getList().iterator());
}
}
}
return false;
}
}
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i = new NestedIterator(nestedList);
* while (i.hasNext()) v[f()] = i.next();
*/
这道题目没能自己做出来。
看了答案后感觉也很难想到。只不过真的很巧妙。
reference:
https://discuss.leetcode.com/topic/44983/share-my-java-neat-solution-8ms
我一直在想，如果list里面还有list，还有list，还有list，一层层迭代进去，what will happen and what can we do?
我本来是想写一个dfs函数，但好像每次输出之后，原状态很难保存下来。这导致的问题是，下一次输出需要依靠这个原状态，如果原状态无法保存，那么下一次也无法输出。
这是 stateful api
we need to store the previous state to get the next state
然后答案里面用到了两个数据结构：
Stack + Iterator
这是第一次我见他们联合使用。
将iterator压入栈中，需要拿下一个元素的时候，就看栈顶的iterator
如果他的 hasNext() 返回false，那么先把他弹出。
如果不是，就取出next元素。
如果是integer，直接返回。
如果不是，那么将他的iterator 再次压入栈中。然后继续循环。
直到找到某个integer或者将栈中所有的iterator全部遍历完，最后返回false
原状态的保存，全部由iterator做到了，我们也不需要再去考虑什么了。
解法很巧妙。
Anyway, Good luck, Richardo! -- 09/06/2016
