0%

【算法笔记】797. 所有可能的路径

今天刷力扣的每日一题797. 所有可能的路径时,发现官方题解用到了Deque,而且用的很巧妙,我大受震撼.jpg

Deque简单来讲就是支持在头和尾进行插入和删除的数据结构,我直接搬出题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
deploy:
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Deque<Integer> stack = new ArrayDeque<Integer>();

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
stack.offerLast(0);
dfs(graph, 0, graph.length - 1);
return ans;
}

public void dfs(int[][] graph, int x, int n) {
if (x == n) {
ans.add(new ArrayList<Integer>(stack)); // new一个List出来保存路径
return;
}
for (int y : graph[x]) {
stack.offerLast(y); // 把目标节点放到stack里
dfs(graph, y, n);
stack.pollLast(); // 目标节点用完就扔,然后找下一个目标节点
}
}
}

之前遇到这种需要记录路径的问题一直束手无策,今天真的茅塞顿开、恍然大悟,居然可以把节点用完就扔,只用一个Deque就能维护路径(虽然这题用栈就够用了,多了解一种数据结构总没毛病)