LEETCODE 1466. Reorder Routes to Make All Paths Lead to the City Zero 解题思路分析

题目大意:

重新规划路线

n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。

路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。

今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0 。

请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

示例 1:

输入:n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出:3
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例 2:

输入:n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出:2
解释:更改以红色显示的路线的方向,使每个城市都可以到达城市 0 。

示例 3:

输入:n = 3, connections = [[1,0],[2,0]]
输出:0

提示:

  • 2 <= n <= 5 * 10^4
  • connections.length == n-1
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] <= n-1
  • connections[i][0] != connections[i][1]

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1466

解题思路分析:

题目描述中很明确的表示出这是一道树型结构问题,对于任意的树形结构,实际上都可以理解为一个有向图,所有路径的方向都是从根节点指向叶子节点。而本题有些特殊,路径的方向是叶子节点指向根节点,但这并不影响解题,因为在树形结构中,从任意一个节点到达根节点的路径都是有且只有一条,反过来,从根节点到任意一个节点的路径也是具有唯一性。因此本题我们同样可以从根节点向每一个叶子节点的方向进行dfs遍历。

解题时,我们首先需要构建出树形结构,利用题目给出的connections路径数组,找出每一个点能够直接连接到的其他点的集合。由于本题的特殊性,这里需要注意一点,在保存其他临节点集合时,除了需要记录临节点编号之外,我们还需要记录下当前点到临节点间路径的方向,比如1代表路径方向为当前节点到临节点,2代表临节点到当前节点。

构建好树形结构后,我们从根节点开始进行熟悉的dfs遍历操作。在每一层的dfs递归中,首先从树形结构中找出当前节点的所有临节点集合,查看当前节点与其组成路径的方向,如果方向为1(当前节点指向临节点),说明不符合题意,这是一条需要重新规划的路线,因此返回结果加一。反之,代表当前路径已经符合要求。dfs完所有节点后,也就能够统计出所有不符合题意的节点个数。另外解题时还要注意一下dfs的方向,如果临节点集合中存在当前节点的父节点,则跳过该节点,避免逆向遍历。

实现代码:

public int minReorder(int n, int[][] connections) {
    List<int[]>[] map=new ArrayList[n]; // 记录每个节点的临节点
    for(int[] c : connections){ // 遍历每一条路径
        // 路径起点与终点
        int from=c[0],to=c[1];
        // 找到起点的临节点集合
        if(map[from]==null)map[from]=new ArrayList<>();
        // 将终点加入到起点的临节点集合,并设置路径方向为1
        map[from].add(new int[]{to,1});
        // 找到终点的临节点集合
        if(map[to]==null)map[to]=new ArrayList<>();
        // 将起点加入到终点的临节点集合,并设置路径方向为2
        map[to].add(new int[]{from,2});
    }
    return dfs(map,0,0); // dfs求解
}
// map:树形结构
// node:当前节点
// parent:当前节点的父节点
// 返回结果:当前节点下需要修改的路径数
int dfs(List<int[]>[] map, int node, int parent){
    // 当前节点的临节点集合
    List<int[]> list=map[node];
    int res=0; // 返回结果
    for(int[] city : list){ // 循环每一个临节点
        // 如果临节点是父节点,跳过(不走回头路)
        if(city[0]==parent) continue;
        // 如果到临节点的路径为顺方向,返回结果加一
        // 顺方向代表从根节点到叶子节点方向,与题目要求相反
        if(city[1]==1) res++;
        // dfs到临节点,并累加子问题结果
        res+=dfs(map,city[0],node);
    }
    return res;
}

本题解法执行时间为33ms。

Runtime: 33 ms, faster than 83.01% of Java online submissions for Reorder Routes to Make All Paths Lead to the City Zero.

Memory Usage: 60.7 MB, less than 100.00% of Java online submissions for Reorder Routes to Make All Paths Lead to the City Zero.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1466-reorder-routes-to-make-all-paths-lead-to-the-city-zero-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。