博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
210. Course Schedule II
阅读量:5813 次
发布时间:2019-06-18

本文共 1893 字,大约阅读时间需要 6 分钟。

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]4, [[1,0],[2,0],[3,1],[3,2]]There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Topo-sort 在leetcode里只有几个题目,而且逻辑完全一样。只要清楚的记得几大步骤就可以解题啦。1. 建立入度indegree.2. 组成cousePairs,把原来输入的无规律edges,转换成 out -> List
另一种表示图的方法。3. 找到indegree为零的点,放到Queue里,也就是我们topo-sort 图的入口。4. 从Q里弹出点,写到结果里。对于它的neighbors, 也就是out指向的in。这里题目意思是preCourses, 因为我们已经上过这门课,所以需要上的课也就少了一门。如果这些neighbors的入度也变成0,也就变成了新的入口,加入到Q里,重复4.5. 返回结果。
public class Solution {    public int[] findOrder(int num, int[][] pres) {        int[] res = new int[num];                int[] indegree = new int[num];        List
[] pairs = new List[num]; for(int[] pre : pres){ // pre[0] in, pre[1] out int in = pre[0], out = pre[1]; indegree[in]++; if(pairs[out] == null) pairs[out] = new ArrayList
(); pairs[out].add(in); } Queue
q = new LinkedList<>(); for(int i = 0; i < num; i++){ if(indegree[i] == 0) q.offer(i); } int t = 0; while(!q.isEmpty()){ int out = q.poll(); res[t++] = out; if(pairs[out] == null) continue; // 这里题目有可能没有预修课,可以直接上任意课程。 for(int in : pairs[out]){ indegree[in]--; if(indegree[in] == 0) q.offer(in); } } return t == num ? res : new int[0]; }}

转载地址:http://tttbx.baihongyu.com/

你可能感兴趣的文章
Java访问文件夹中文件的递归遍历代码Demo
查看>>
项目笔记:测试类的编写
查看>>
通过容器编排和服务网格来改进Java微服务的可测性
查看>>
re:Invent解读:没想到你是这样的AWS
查看>>
PyTips 0x02 - Python 中的函数式编程
查看>>
阿里云安全肖力:安全基础建设是企业数字化转型的基石 ...
查看>>
使用《Deep Image Prior》来做图像复原
查看>>
如何用纯 CSS 为母亲节创作一颗像素画风格的爱心
查看>>
Linux基础命令---rmdir
查看>>
iOS sqlite3(数据库)
查看>>
粤出"飞龙",打造新制造广东样本
查看>>
编玩边学获数千万元A轮融资,投资方为君联资本
查看>>
蓝图(Blueprint)详解
查看>>
Spark之SQL解析(源码阅读十)
查看>>
Android图片添加水印图片并把图片保存到文件存储
查看>>
比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第二部分:代码实现(C语言)...
查看>>
海贼王十大悲催人物
查看>>
BigDecimal 舍入模式(Rounding mode)介绍
查看>>
开源 免费 java CMS - FreeCMS1.2-标签 infoSign
查看>>
开源 免费 java CMS - FreeCMS1.9 移动APP生成栏目列表数据
查看>>