wordpress网站不显示系列,宁波专业网站搭建地址,呼叫中心网站建设,网站导航一定要一样吗这个题是图的问题#xff0c;因为图的拓扑排序在实际应用中有非常多的用途图#xff0c;所以最近考的越来越多
解法都在代码里#xff0c;不懂就留言或者私信
看这个题之前一定要好好看看207题我写的题解#xff0c;也许207看懂了的话#xff0c;210只是一个coding问题了…这个题是图的问题因为图的拓扑排序在实际应用中有非常多的用途图所以最近考的越来越多
解法都在代码里不懂就留言或者私信
看这个题之前一定要好好看看207题我写的题解也许207看懂了的话210只是一个coding问题了
Leetcode面试经典150题-207.课程表-CSDN博客
一定要看!一定要看一定要看
class Solution {/**其实这个题一看就是第207题课程表的复杂版本那么这个题和那个题有什么明显的不同呢不同就是那个题问的是能不能完成而这个题问的是按什么顺序完成其实原理都是一样的我们只需要把过程中弹出的入度为0的课程依次记录到数组里就行*/public int[] findOrder(int numCourses, int[][] prerequisites) {/**如果只有一个课程拿这个课程当然能完成他的编号为0*/if(numCourses 1) {return new int[]{0};}/**如果大于一个课程的话我们还是按照解207题的方法先包装一个课程类出来然后把课程表里的入度为0的先弹出*//**先定义一个hashMap用来把所有有依赖关系的课程及其依赖初始化一下没在hashMap里的就是不依赖其他的都是可以完成的key是课程编号value是真正的课程我们初始化的过程中会把他依赖多少门课以及哪些具体的课程依赖他都确定了*/MapInteger, Course map new HashMap();for(int[] prerequisite : prerequisites) {/**prerequisite是一条具体的依赖关系prerequisite[0]依赖于prerequisite[1]*//**依赖者、被依赖者如果还没有创建Course对象就先创建因为我们后面的操作都是以Course来的 */if(!map.containsKey(prerequisite[0])) {Course course new Course(prerequisite[0]);map.put(prerequisite[0], course);}if(!map.containsKey(prerequisite[1])) {Course course new Course(prerequisite[1]);map.put(prerequisite[1], course);}/**两个课程都有了我们就可以初始化他们之间的关系了对于依赖别人的记录一下他到底依赖了多少课程也就是它的入度*/map.get(prerequisite[0]).inDegree ;/**被别人依赖的课程的next增加依赖者*/map.get(prerequisite[1]).nexts.add(map.get(prerequisite[0]));}/**定义结果数组*/int[] ans new int[numCourses];/**当前有效长度以及下个要填的位置 */int curLen 0;/**遍历一下0~numCourses-1,把没有依赖关系的先放到结果指定位置*/for(int i 0; i numCourses; i) {if(!map.containsKey(i)) {ans[curLen ] i;}}/**队列里全是入度为0的 */QueueCourse zeroInQueue new LinkedList();/**用一个遍历count记录多少个记录入过队列 */int count 0;/**遍历hashMap把入队为0的入队*/for(Course course : map.values()) {if(course.inDegree 0) {zeroInQueue.offer(course);}}/**弹出队列中的课程并在弹出时加入答案同时减少依赖的入度*/while(!zeroInQueue.isEmpty()) {Course course zeroInQueue.poll();/**课程编号加入结果 */ans[curLen ] course.courseNo;count ;/**把依赖它的课程拿出并把这些依赖性的课程的入队-1*/for(Course next : course.nexts) {next.inDegree --;/**如果就依赖当前课程那减完就是0了也符合入队为0的条件 */if(next.inDegree 0) {/**注意我们是在弹出的时候加入结果这里别加 */zeroInQueue.offer(next);}}}/**如果所有的在hashmap中的课程都入过zeroInQueue说明他们都能完成返回ans即可否则整个完不成返回空数组 */return count map.size()? ans : new int[]{};}static class Course {int courseNo;int inDegree;ListCourse nexts;public Course(int courseNo) {this.courseNo courseNo;this.nexts new ArrayList();}}
}
结果一般因为我利用的数据结构太多了可以自己考虑改成数组或者别的来代替我这边着急刷先不优化了毕竟面试没几个人管你的常数时间
