W**********2
发帖数: 30 | 1 题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：） |
j******o
发帖数: 4219 | |
f*y
发帖数: 876 | 3 用两个Queue，
Queue // the NestList of the next element
Queue // the index of the next element |
d******o
发帖数: 13 | 4 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
d******o
发帖数: 13 | 5 Stack + 递归
stack中存储的是iterate 时，当前所处的 List 及 position，可能指向的是Node，可
能是List，可能当前的position ＝＝ list.size() 也可能 stack 已为空。
分别对以上情况做处理即可。 |
f*******r
发帖数: 976 | 6 Mark
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
S********t
发帖数: 3431 | 7 list个毛线，直接说nary tree嘛。
tree怎么做iterator不是基础知识吗？
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
g*****i
发帖数: 91 | |
g*****i
发帖数: 91 | |
f*********s
发帖数: 1881 | 10 mark
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
|
|
W**********2
发帖数: 30 | 11 题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：） |
j******o
发帖数: 4219 | |
f*y
发帖数: 876 | 13 用两个Queue，
Queue // the NestList of the next element
Queue // the index of the next element |
d******o
发帖数: 13 | 14 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
d******o
发帖数: 13 | 15 Stack + 递归
stack中存储的是iterate 时，当前所处的 List 及 position，可能指向的是Node，可
能是List，可能当前的position ＝＝ list.size() 也可能 stack 已为空。
分别对以上情况做处理即可。 |
f*******r
发帖数: 976 | 16 Mark
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
S********t
发帖数: 3431 | 17 list个毛线，直接说nary tree嘛。
tree怎么做iterator不是基础知识吗？
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
g*****i
发帖数: 91 | |
g*****i
发帖数: 91 | |
f*********s
发帖数: 1881 | 20 mark
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
|
|
y*******5
发帖数: 887 | 21 用composition pattern:
1:---
package NestedIterator;
public interface NestedNodeList extends Iterable {
}
2:---
package NestedIterator;
import java.util.Iterator;
public class Node implements NestedNodeList {
private E val;
public Node(E val) {
this.val = val;
}
@Override
public Iterator iterator() {
return new NodeIterator();
}
private class NodeIterator implements Iterator {
private boolean iterated = false;
@Override
public boolean hasNext() {
return !iterated;
}
@Override
public E next() {
if (hasNext()) {
iterated = true;
return val;
}
return null;
}
}
}
3.---
package NestedIterator;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class NodeList implements NestedNodeList {
private List> nodeList;
public NodeList() {
this.nodeList = new ArrayList<>();
}
@Override
public Iterator iterator() {
return new NodeListIterator();
}
public void add(NestedNodeList nodes) {
nodeList.add(nodes);
}
private class NodeListIterator implements Iterator {
private int idx = 0;
Iterator iter;
@Override
public boolean hasNext() {
if (idx >= nodeList.size())
return false;
if (iter == null)
iter = nodeList.get(idx).iterator();
if (iter.hasNext())
return true;
idx += 1;
if (idx >= nodeList.size())
return false;
iter = nodeList.get(idx).iterator();
return iter.hasNext();
}
@Override
public E next() {
if (hasNext()) {
return iter.next();
}
return null;
}
}
public static final void main(String[] args) {
NodeList list0 = new NodeList<>();
NodeList list1 = new NodeList<>();
NodeList list2 = new NodeList<>();
NodeList list3 = new NodeList<>();
Node node0 = new Node<>(0);
Node node1 = new Node<>(1);
Node node2 = new Node<>(2);
Node node3 = new Node<>(3);
Node node4 = new Node<>(4);
Node node5 = new Node<>(5);
Node node6 = new Node<>(6);
list3.add(node5);
list3.add(node6);
list2.add(node4);
list2.add(list3);
list2.add(node4);
list2.add(list3);
list1.add(node1);
list1.add(node2);
list0.add(node0);
list0.add(list1);
list0.add(node3);
list0.add(list2);
for (int i : list0) {
System.out.println(i);
}
}
}
定义一个interface， 把node 和 list of node 定义在同一个interface下
这个interface里面只有一个method 就是 iterator
Interface NestedNodeList
然后，node的类型的iterator的实现是：
iterator里面有个bool变量
如果这个node已经取过了，就是true，没有取过就是false
node iterator 的 hasnext()方法就是用这个bool来判断
next()的方法就返回 node的值并把这个bool的状态更新
然后NodeList 用一个private 的list 放入 NestedNodeList 为interface的类型
所以既可以放入node， 也可以放入里一个nested Nodelist本身
然后NodeList的iterator就是 深度优先 dfs 的遍历这个list
recursive的call list里面的每个iterator
【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
: 好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
|
m********r
发帖数: 29 | |
r********g
发帖数: 219 | 23 大体这样(java)：
public class SuperIterator {
Stack iterators = new Stack<>();
public SuperIterator(Iterator topIterator) {
iterators.push(topIterator);
}
public boolean hasNext() {
if (iterators.isEmpty()) {
return false;
}
Iterator topIterator = iterators.pop();
while (!topIterator.hasNext()) {
if (!iterators.isEmpty()) {
topIterator = iterators.pop();
} else {
return false;
}
}
iterators.push(topIterator);
return true;
]
// 以此类推 写出 next()
} |
a******f
发帖数: 9 | 24 #include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class NestedInteger {
public:
NestedInteger(int i) : integer(i), isInt(true) {}
NestedInteger(vector l) : nestedList(l), isInt(false) {}
// Return true if this NestedInteger holds a single integer, rather than
a nested list.
bool isInteger() {
return isInt;
}
// Return the single integer that this NestedInteger holds, if it holds
a single integer
// The result is undefined if this NestedInteger holds a nested list
int getInteger() {
return integer;
}
// Return the nested list that this NestedInteger holds, if it holds a
nested list
// The result is undefined if this NestedInteger holds a single integer
vector &getList() {
return nestedList;
}
bool isInt;
int integer;
vector nestedList;
};
class NestedIntegerIterator {
public:
NestedIntegerIterator(vector &nestedList) {
s.push({nestedList.begin(), nestedList.end()});
}
int next() {
return (s.top()[0]++)->getInteger();
}
bool hasNext() {
while (!s.empty()) {
while (!s.empty() && s.top()[0] == s.top()[1]) {
s.pop();
if (!s.empty())
++s.top()[0];
}
if (!s.empty() && s.top()[0]->isInteger())
return true;
while (!s.empty() && !s.top()[0]->isInteger())
s.push({s.top()[0]->getList().begin(), s.top()[0]->getList()
.end()});
}
return false;
}
private:
stack::iterator>> s;
};
int main()
{
{
vector l = {NestedInteger(0), NestedInteger({
NestedInteger(1), NestedInteger(2)}), NestedInteger(3), NestedInteger({
NestedInteger(4), NestedInteger({NestedInteger(5), NestedInteger(6)})})};
NestedIntegerIterator ni(l);
while (ni.hasNext())
cout << ni.next() << endl;
}
return 0;
} |
