797. 所有可能的路径

题目

给一个有 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.

提示:

  1. 结点的数量会在范围 [2, 15] 内。
  2. 你可以把路径以任意顺序输出,但在路径内的结点的顺序必须保证。

难点:一开始,怎么也理解不了题目的意思,后来琢磨半天,就是从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);
    }
}

leetcode执行结果

执行用时 : 12 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2.7 MB , 在所有 Rust 提交中击败了 100.00% 的用户

遇到难点

  1. 读不懂题目

leetcode相似题型

575. 分糖果
224. 基本计算器
467. 环绕字符串中唯一的子字符串

2019-09-10 10:12

留言