南昌网站建设模板服务商,物流网站免费源码,影院wordpress,比亚迪电子股票Leetcode 1466. 重新规划路线#xff08;两种思路#xff1a;正难则反 DFS 无向图转有向图 / DFS 无向建图 设定权值 反向遍历#xff09;题目解法一#xff1a; 正难则反 DFS 无向图转有向图#xff1a;第 1 步#xff1a;先建立一个无向图 G0第 2 步#xff1a;从…Leetcode 1466. 重新规划路线两种思路正难则反 DFS 无向图转有向图 / DFS 无向建图 设定权值 反向遍历题目解法一 正难则反 DFS 无向图转有向图第 1 步先建立一个无向图 G0第 2 步从 0 开始走无向图 G0直到所有节点记录此时经过的所有边形成有向图 G1第 3 步建立原图的有向图 G2第 4 步遍历每个点记录 G2 改成 G1 需要修改的边数 edge 遍历每个点 p将 G1 从 p 可以转到的点放入 set遍历 G2 从 p 可以转移到的点去 map 中删除不在 set 则不删set 剩下的元素个数则是 G2 需要修改的个数 此边数为重新规划后的反向图应该修改的边数注意仅有一种修改结果第 5 步答案就是total(即 n-1) - edge时间复杂度On空间复杂度On 代码一
/*** 正难则反 DFS 无向图转有向图** 第 1 步* 先建立一个无向图 G0** 第 2 步* 从 0 开始走无向图 G0直到所有节点* 记录此时经过的所有边形成有向图 G1** 第 3 步* 建立原图的有向图 G2** **第 4 步*** 遍历每个点记录 G2 改成 G1 需要修改的边数 edge* * 遍历每个点 p* * 将 G1 从 p 可以转到的点放入 set* * 遍历 G2 从 p 可以转移到的点去 map 中删除不在 set 则不删* * set 剩下的元素个数则是 G2 需要修改的个数* 此边数为重新规划后的**反向图**应该修改的边数* 注意仅有一种修改结果** 第 5 步* 答案就是total(即 n-1) - edge* 时间复杂度On空间复杂度On**/public int minReorder(int n, int[][] connections) {// 先建立一个无向图 G0ListInteger[] treeList0 buildTree(n, connections);// 从 0 开始走无向图直到所有节点记录此时经过的所有边形成有向图 G1ListInteger[] treeList1 new ArrayList[n];for (int i 0; i n; i) {treeList1[i] new ArrayList();}dfsTraversalTree(0, -1, treeList0, treeList1);// 建立原图的有向图 G2ListInteger[] treeList2 buildDirectedTree(n, connections);// 遍历每个点记录 G2 改成 G1 需要修改的边数 edgeint res 0;SetInteger pointSet new HashSet();for (int i 0; i n; i) {for (int point : treeList1[i]) {pointSet.add(point);}for (int point : treeList2[i]) {pointSet.remove(point);}res pointSet.size();pointSet.clear();}return n - 1 - res;}/*** 建立有向图*/private ListInteger[] buildDirectedTree(int n, int[][] edges) {ListInteger[] edgeList new ArrayList[n];for (int i 0; i n; i) {edgeList[i] new ArrayList();}for (int i 0; i edges.length; i) {int u edges[i][0];int v edges[i][1];edgeList[u].add(v);}return edgeList;}/*** 从 0 开始走无向图直到所有节点记录此时经过的所有边形成有向图 G1*/private void dfsTraversalTree(int son, int father, ListInteger[] treeList0, ListInteger[] treeList1) {for (int next : treeList0[son]) {if (next ! father) {treeList1[son].add(next);dfsTraversalTree(next, son, treeList0, treeList1);}}}/*** 建立无向图*/private ListInteger[] buildTree(int n, int[][] edges) {ListInteger[] edgeList new ArrayList[n];for (int i 0; i n; i) {edgeList[i] new ArrayList();}for (int i 0; i edges.length; i) {int u edges[i][0];int v edges[i][1];edgeList[u].add(v);edgeList[v].add(u);}return edgeList;}解法二 DFS 无向建图 设定权值 反向遍历:第 1 步建立无向图 G注意无环无重边将正向边权值设为 1反向边权值设为 0第 2 步从 0 开始走到所有的点记录权值总和就是结果因为走的是需要结果的反向图需要所有点到 0因此走到正向边代表此边需要反转、走到反向边则不需要时间复杂度On空间复杂度On 代码二
/*** DFS 无向建图 设定权值 反向遍历:** 第 1 步* 建立无向图 G注意无环无重边* 将正向边权值设为 1反向边权值设为 0** 第 2 步* 从 0 开始走到所有的点记录权值总和就是结果* 因为走的是需要结果的反向图需要所有点到 0因此走到正向边代表此边需要反转、走到反向边则不需要* 时间复杂度On空间复杂度On**/public int minReorder(int n, int[][] connections) {// 建无向图将正向边权值设为 1反向边权值设为 0ListPairInteger, Integer[] treeWeightList buildWeightTree(n, connections);// 从 0 开始走到所有的点记录权值总和就是结果return dfsTraversalWeightTree(0, -1, treeWeightList);}/*** 从 0 开始走到所有的点记录权值总和就是结果*/private int dfsTraversalWeightTree(int son, int father, ListPairInteger, Integer[] treeList) {int res 0;for (PairInteger, Integer nextPair : treeList[son]) {int next nextPair.getKey();int weight nextPair.getValue();if (next ! father) {res weight dfsTraversalWeightTree(next, son, treeList);}}return res;}/*** 建无向图将正向边权值设为 1反向边权值设为 0*/private ListPairInteger, Integer[] buildWeightTree(int n, int[][] edges) {ListPairInteger, Integer[] edgeList new ArrayList[n];for (int i 0; i n; i) {edgeList[i] new ArrayList();}for (int i 0; i edges.length; i) {int u edges[i][0];int v edges[i][1];edgeList[u].add(new Pair(v, 1));edgeList[v].add(new Pair(u, 0));}return edgeList;}
