给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了a→b你就不能从b→a）空就是没有下一个结点了。
示例:
输入: [[1,2], [3], [3], []]
输出: [[0,1,3],[0,2,3]]
解释: 图是这样的:
0--->1
| |
v v
2--->3
这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.
提示:
难点：一开始，怎么也理解不了题目的意思，后来琢磨半天，就是从0到n节点的路径，但是在做题过程中很困惑，比如：
输入： [[3,1],[4,6,7,2,5],[4,6,3],[6,4],[7,6,5],[6],[7],[]] 输出结果里面却没有 [0,3,7]这个结果，但是路径里面是没有的，后面看了题目的英文原来的意思，才发现被中文的题目给坑了，英文原来的题目描述是这样的：
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
意思清晰明了，给到的graph图数据是从0,1....到graph.length-1, graph[i]是一个nodes[j]节点列表，然后就存在边 (i,j)。也就是存在路径(i,j)，终于明白为啥没有[0,3,7]这个结果, 因为就没有这条边。i既是序号，又是节点中的值，我们是要拿着值找到graph[i]位置的nodes节点列表，直到值就是最终点。既然是按图画出来的边，那么就不用考虑会不会重复的问题。
题型归类: 循环，递归
从起点0开始, 获取第0个node的vec，然后循环取出vec里面的每一个值i，如果是最后一个数字了，那么就结束了，保存这个路径，否则，拿着这个数字，找到i这个数字对应的node，然后继续（如果是最后一个数字，那么就结束，并保存路径，否则继续找到对应的node）...，需要主要的是，每次循环是一个新的路线的创建。
// 代码实现
/// author arlicle
/// https://www.debugmyself.com
/// https://github.com/arlicle
impl Solution {
pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = vec![];
let last_num = (graph.len() as i32) - 1;
loop_vec(0, vec![0], &graph, last_num, &mut result);
result
}
}
fn loop_vec(current_num: usize, res: Vec<i32>, graph: &Vec<Vec<i32>>, last_num: i32, result: &mut Vec<Vec<i32>>) {
// 如果不是最后一个数据，那么就继续往下找
for i in graph[current_num].iter() {
// 列表中每一个数据相当于开展了一条新的线
let mut a = res.clone(); // 新创新的路线
a.push(*i);
if (*i == last_num) {
// 如果当前数据为最后一个数据，就把当前路径的数据保存到结果列表
result.push(a);
continue
}
// 如果还没有到终点，继续顺着点往下
loop_vec(*i as usize, a, graph, last_num, result);
}
}
执行用时 : 12 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2.7 MB , 在所有 Rust 提交中击败了 100.00% 的用户
575. 分糖果
224. 基本计算器
467. 环绕字符串中唯一的子字符串
2019-09-10 10:12