1466. 重新规划路线 --力扣 --JAVA

简介: n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0 。请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

 题目

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

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

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

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

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

解题思路

    1. 选择一个数据结构数组用来存储可到达0的所有节点,为便于编写首先需添加元素0;
    2. while循环持续遍历整个路径数组,将可到达的添加到数据结构中,记录添加的数量,用来跳出循环(左右指针遍历可能会缩减时间);

    代码展示

    class Solution {
        public int minReorder(int n, int[][] connections) {
            boolean[] road = new boolean[n];
            road[0] = true;
            int count = 1;
            int ans = 0;
            while (count < n){
                for (int[] connection : connections) {
                    //可直接到达或经过其他节点到达
                    if (road[connection[1]]) {
                        if(road[connection[0]]){
                            continue;
                        }
                        road[connection[0]] = true;
                        count++;
                    } else if (road[connection[0]]) {      //不可达则+1
                        ans++;
                        road[connection[1]] = true;
                        count++;
                    }
                }
            }
            return ans;
        }
    }

    image.gif


    目录
    相关文章
    |
    2月前
    |
    算法 Java
    [Java·算法·简单] LeetCode 9. 回文数 详细解读
    [Java·算法·简单] LeetCode 9. 回文数 详细解读
    22 0
    |
    2月前
    |
    Java
    383. 赎金信 --力扣 --JAVA
    给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能c里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。
    22 1
    |
    9天前
    |
    Java
    LeetCode题解-逆波兰表达式求值-Java
    逆波兰表达式求值-Java
    7 0
    |
    9天前
    |
    Java
    |
    9天前
    |
    Java
    |
    9天前
    |
    Java
    LeetCode题解-二叉搜索树中第K小的元素-Java
    LeetCode题解-二叉搜索树中第K小的元素-Java
    6 0
    |
    9天前
    |
    Java
    |
    9天前
    |
    Java
    LeetCode题解- 两两交换链表中的节点-Java
    两两交换链表中的节点-Java
    7 0
    |
    9天前
    |
    Java
    LeetCode题解-合并K个有序数组-Java
    合并K个有序数组-Java
    5 0
    |
    9天前
    |
    Java

    相关产品

  1. 云迁移中心