LeetCode 207:课程表(图论,利用拓扑排序判断是否有环)

2024-02-09 13:44

本文主要是介绍LeetCode 207:课程表(图论,利用拓扑排序判断是否有环),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
示例 2:

输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

提示:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

思路

利用拓扑排序来判断是否成环,如果成环的话,拓扑排序返回的节点列表的数量会少于图的节点树。所以先构建图,然后拓扑排序返回所有不成环的节点列表。

代码

第一版代码

class Solution {public class Graph{public HashMap<Integer,Node> nodes;public HashSet<Edge> edges;public Graph(){nodes = new HashMap<>();edges = new HashSet<>();}}public class Node{public int value;public int in;public int out;public ArrayList<Node> nexts;public ArrayList<Edge> edges;public Node(int value){this.value = value;in=0;out=0;nexts = new ArrayList<>();edges = new ArrayList<>();}}public class Edge{public Node from;public Node to;public Edge(Node from, Node to){this.from = from;this.to = to;}}public HashSet<Integer> top(Graph graph){HashMap<Node,Integer> inMap = new HashMap<>();//一个节点对应的剩余的入度Queue<Node> zeroInQueue = new LinkedList<>();//存放着入度为0的节点for(Node node:graph.nodes.values()){inMap.put(node, node.in);if(node.in==0) zeroInQueue.add(node);}HashSet<Integer> result = new HashSet<>();//存放结果while(!zeroInQueue.isEmpty()){Node cur = zeroInQueue.poll();result.add(cur.value);for(Node next:cur.nexts){int newin = inMap.get(next)-1;inMap.put(next,newin);if(newin==0) zeroInQueue.add(next);}}return result;}public Graph createGraph(int[][] prerequisites){Graph graph = new Graph();for(int i=0;i<prerequisites.length;i++){int fromVal = prerequisites[i][1];int toVal = prerequisites[i][0]; if(!graph.nodes.containsKey(fromVal)) graph.nodes.put(fromVal, new Node(fromVal));if(!graph.nodes.containsKey(toVal)) graph.nodes.put(toVal, new Node(toVal));Node fromNode = graph.nodes.get(fromVal);Node toNode = graph.nodes.get(toVal);Edge edge = new Edge(fromNode, toNode);fromNode.out++;toNode.in++;graph.edges.add(edge);fromNode.nexts.add(toNode);fromNode.edges.add(edge);}return  graph;}public boolean canFinish(int numCourses, int[][] prerequisites) {if(prerequisites.length==0) return true;Graph graph = createGraph(prerequisites);HashSet<Integer> nodes = top(graph);// myPrint(nodes);// int nums = nodes.size();// if(numCourses==nums||numCourses-1==nums) return true;HashSet<Integer> targets = new HashSet<>(); for(int i=0;i<prerequisites.length;i++){int preVal = prerequisites[i][0];int laterVal = prerequisites[i][1];targets.add(preVal);targets.add(laterVal);}if(targets.equals(nodes)) return true;return false;}public void myPrint(HashSet<Node> nodes){for(Node node: nodes){System.out.println(node.value);}}
}

执行用时分布,17ms,击败10.60%使用 Java 的用户。
需要优化

第二版代码

感觉第一版代码得出targets列表是多余的,因为只要判断图的节点的数量和拓扑排序的不成环的节点的数量是否一致。所以top排序返回数量即可。此外,删除节点中不必要的属性。

class Solution {public class Graph{public HashMap<Integer,Node> nodes;public HashSet<Edge> edges;public Graph(){nodes = new HashMap<>();edges = new HashSet<>();}}public class Node{public int value;public int in;public ArrayList<Node> nexts;public Node(int value){this.value = value;in=0;nexts = new ArrayList<>();}}public class Edge{public Node from;public Node to;public Edge(Node from, Node to){this.from = from;this.to = to;}}public int top(Graph graph){HashMap<Node,Integer> inMap = new HashMap<>();//一个节点对应的剩余的入度Queue<Node> zeroInQueue = new LinkedList<>();//存放着入度为0的节点for(Node node:graph.nodes.values()){inMap.put(node, node.in);if(node.in==0) zeroInQueue.add(node);}int ans=0;while(!zeroInQueue.isEmpty()){Node cur = zeroInQueue.poll();ans++;for(Node next:cur.nexts){int newin = inMap.get(next)-1;inMap.put(next,newin);if(newin==0) zeroInQueue.add(next);}}return ans;}public Graph createGraph(int[][] prerequisites){Graph graph = new Graph();for(int i=0;i<prerequisites.length;i++){int fromVal = prerequisites[i][1];int toVal = prerequisites[i][0]; if(!graph.nodes.containsKey(fromVal)) graph.nodes.put(fromVal, new Node(fromVal));if(!graph.nodes.containsKey(toVal)) graph.nodes.put(toVal, new Node(toVal));Node fromNode = graph.nodes.get(fromVal);Node toNode = graph.nodes.get(toVal);Edge edge = new Edge(fromNode, toNode);toNode.in++;graph.edges.add(edge);fromNode.nexts.add(toNode);}return  graph;}public boolean canFinish(int numCourses, int[][] prerequisites) {if(prerequisites.length==0) return true;Graph graph = createGraph(prerequisites);int realnum = top(graph);int num = graph.nodes.size();if(realnum==num) return true;return false;}
}

13ms,击败15.27%使用 Java 的用户。
可以看到优化的不多,毕竟自己是套的所有图基本都可以用的板子,想要优化的话就得改动这个存储数据结构,不方便自己记忆板子。但读者可以自行选择,我有提供其他数据结构实现的代码,在第三版。

第三版代码

public class Solution {public static boolean canFinish(int numCourses, int[][] prerequisites) {// 构建图ArrayList<ArrayList<Integer>> graph = new ArrayList<>();int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}for (int[] prerequisite : prerequisites) {int from = prerequisite[1];int to = prerequisite[0];graph.get(from).add(to);inDegree[to]++;}// 使用拓扑排序判断是否能够完成所有课程Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}int count = 0;while (!queue.isEmpty()) {int course = queue.poll();count++;for (int neighbor : graph.get(course)) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.offer(neighbor);}}}return count == numCourses;}
}

5ms,击败52.30%使用 Java 的用户。

这篇关于LeetCode 207:课程表(图论,利用拓扑排序判断是否有环)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/694385

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists