LeetCode:210课程表Ⅱ(图论:拓扑排序判断是否有环)

2024-02-09 14:36

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

做本题之前最好先做了LeetCode:207课程表,见本人另一篇博客http://t.csdnimg.cn/vSXgN

题目

现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。

例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:

输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3:

输入:numCourses = 1, prerequisites = []
输出:[0]

提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

思路

这道题和LC207不同的是,它需要返回拓扑排序的路径。除此之外,不在拓扑排序路径,或者说不在图中的节点也需要返回,但是无所谓插入的顺序。所以本人在最后判断了一下哪些节点没有在图中出现,然后插入在了拓扑排序节点数组的最后面。
注意返回空数组是return new int[0]不是return null;

代码

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 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 int[] findOrder(int numCourses, int[][] prerequisites) {int[] result = new int[numCourses];//存放结果Graph graph = createGraph(prerequisites);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 realnum=0;//拓扑排序路径的节点,即不成环的节点数量while(!zeroInQueue.isEmpty()){Node cur = zeroInQueue.poll();result[realnum]=cur.value;realnum++;for(Node next:cur.nexts){int newin = inMap.get(next)-1;inMap.put(next,newin);if(newin==0) zeroInQueue.add(next);}}int num = graph.nodes.size();if(realnum!=num) return new int[0];//如果不成环的节点数和图中的节点数不相等,说明有环存在,返回一个空数组。int res=0;//res表示其他没在图中出现的节点的数量if(numCourses!=num){//如果课程数和图的节点数不相等,直接判断是哪些节点没有在图中出现,插入到result最后面。for(int i=0;i<numCourses;i++){if(!graph.nodes.containsKey(i)) {result[realnum+res]=i;res++;}}}return result;}
}

13ms,击败14.65%使用 Java 的用户

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



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

相关文章

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.