2023年12月7日每日一题--1466. 重新规划路线

1466. 重新规划路线

题目分析

树形结构，广度优先搜索或者深度优先搜索。本题采用深度优先搜索。

从节点0开始，对其进行深度优先搜索。

方案一

运行超时了，原因在于对当前节点进行查找的时候时间复杂度过高，导致了时间超时。

class Solution {

    int result = 0;
    boolean[] used;
    int sum = 1;
    int[][] Connections;

    public int minReorder(int n, int[][] connections) {
        used = new boolean[n];
        used[0] = true;

        Connections = connections;
        fun(0);

        return result;
    }

    public void fun(int num) {

        for(int i = 0; i < Connections.length; i++) {
            if (Connections[i][1] == num && used[Connections[i][0]] == false) {
                
                used[Connections[i][0]] = true;
                fun(Connections[i][0]);
            }
        }

        for(int i = 0; i < Connections.length; i++) {
            if (Connections[i][0] == num && used[Connections[i][1]] == false) {
                // System.out.println(Connections[i][0] + " " + Connections[i][1]);
                result++;
                used[Connections[i][1]] = true;
                fun(Connections[i][1]);
            }
        }
    }
}

结果

分析

时间复杂度：
O( n ^ 2 )

空间复杂度：
O( n )

方案二

通过时间换空间的方式来减少时间复杂度。

class Solution {

    int result = 0;
    boolean[] used;
    ArrayList<Integer>[][] conList;
    int sum = 1;

    public int minReorder(int n, int[][] connections) {
        used = new boolean[n];
        used[0] = true;


        conList = new ArrayList[n][2];

        for(int i = 0; i < connections.length; i++) {
            
            if (conList[connections[i][0]][0] == null) {
                conList[connections[i][0]][0] = new ArrayList<>();
            }
            conList[connections[i][0]][0].add(connections[i][1]);

            if (conList[connections[i][1]][1] == null) {
                conList[connections[i][1]][1] = new ArrayList<>();
            }
            conList[connections[i][1]][1].add(connections[i][0]);
        }

        fun(0);

        return result;
    }

    public void fun(int num) {

        if (conList[num][0] != null) {
            for (Integer i : conList[num][0]) {
                if (!used[i]) {
                    result++;
                    used[i] = true;
                    fun(i);
                }
            }
        }

        if (conList[num][1] != null) {
            for (Integer i : conList[num][1]) {
                if (!used[i]) {
                    used[i] = true;
                    fun(i);
                }
            }
        }
    }
}

结果

分析

时间复杂度：
O( n)

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/solutions/2553195/zhong-xin-gui-hua-lu-xian-by-leetcode-so-psl6/

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] e = new List[n];
        for (int i = 0; i < n; i++) {
            e[i] = new ArrayList<int[]>();
        }
        for (int[] edge : connections) {
            e[edge[0]].add(new int[]{edge[1], 1});
            e[edge[1]].add(new int[]{edge[0], 0});
        }
        return dfs(0, -1, e);
    }

    public int dfs(int x, int parent, List<int[]>[] e) {
        int res = 0;
        for (int[] edge : e[x]) {
            if (edge[0] == parent) {
                continue;
            }
            res += edge[1] + dfs(edge[0], x, e);
        }
        return res;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。