Java手动实现迭代器。(LeetCode 341)

本文最后更新于:2021年3月31日 晚上

341. 扁平化嵌套列表迭代器


leetCode 341

https://leetcode-cn.com/problems/flatten-nested-list-iterator/

  • 先声明 NestedInteger 的结构(题目给出)
1
2
3
4
5
6
7
8
9
10
11
12
13
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();
}

迭代器(效率最高)

  • 手动遍历,将遍历结果存在集合中,然后生成迭代器,其他操作基于此迭代器即可。
  • 遍历方式是DFS,因为此结构可以联系到数据结构中的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* use Java Iterator
*/
public class NestedIterator implements Iterator<Integer> {

private Iterator<Integer> iterator;

public NestedIterator(List<NestedInteger> nestedList) {
List<Integer> list = new ArrayList<>();
for (NestedInteger node : nestedList) {
DFS(node, list);
}
this.iterator = list.iterator(); // all the operation use list's iterator
}

@Override
public Integer next() {
return iterator.next();
}

@Override
public boolean hasNext() {
return iterator.hasNext();
}

/**
* DFS get every element into List res;
*/
private void DFS(NestedInteger node, List<Integer> res) {
if (node.isInteger()) {
res.add(node.getInteger());
return;
}
for (NestedInteger child : node.getList()) {
DFS(child, res);
}
}

}

队列 + DFS(用队列实现 Iterator)

  • 道理同上,DFS手动遍历,将遍历结果存在队列中
  • 用队列手动实现 iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* use DFS and Queue
*/
public class NestedIterator implements Iterator<Integer> {

Deque<Integer> queue = new ArrayDeque<Integer>();

public NestedIterator(List<NestedInteger> nestedList) {
DFS(nestedList);
}

@Override
public Integer next() {
return hasNext() ? queue.pollFirst() : -1;
}

@Override
public boolean hasNext() {
return !queue.isEmpty();
}

/**
* DFS the nestedList, offer the elements into the queue
*/
private void DFS(List<NestedInteger> nestedList) {
for (NestedInteger elem : nestedList) {
if (elem.isInteger()) { // elem is Integer, offer the queue
queue.addLast(elem.getInteger());
} else { // elem is List, DFS the list and offer the elements into queue
DFS(elem.getList());
}
}
}

}

栈 + 递归 (Stack + Recursion)

  • 不同于队列的是,队列要在初始化阶段,将遍历的结果全部处理好,最后按照顺序进行操作即可。
  • 利用栈的思想是,先将这些 NestedInteger按顺序(倒序)存放在栈中,而要使用里面的元素时,再一步步的拆封出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* use Stack and Recursion
*/
public class NestedIterator implements Iterator<Integer> {

Deque<NestedInteger> stack = new ArrayDeque<NestedInteger>();

public NestedIterator(List<NestedInteger> nestedList) {
for (int i = nestedList.size() - 1; i >= 0 ; i--) {
stack.push(nestedList.get(i));
}
}

@Override
public Integer next() {
return hasNext() ? stack.pop().getInteger() : -1;
}

@Override
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
} else { // stack not empty, judge the peek elem's type(List/Integer)
NestedInteger elem = stack.peek();
if (elem.isInteger()) {
return true;
} else { // peek elem is list, iterate the list to push elem into the stack
elem = stack.pop();
List<NestedInteger> list = elem.getList();
for (int i = list.size() - 1; i >= 0; i--) {
stack.push(list.get(i));
}
return hasNext();
}
}
}

}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!