【Leetcode刷题篇】leetcode210 课程表II
发布日期:2021-06-29 15:34:48
浏览次数:4
分类:技术文章
本文共 2896 字,大约阅读时间需要 9 分钟。
现在你总共有 n 门课需要选,记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。
示例 1:
输入: 2, [[1,0]] 输出: [0,1] 解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3] 解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。 你可以假定输入的先决条件中没有重复的边。
解题思路:
- 每个课程对应图中的一个结点
- 先修要求构成有向边
- 拓扑排序:对于有向图的结点按照访问顺序排序
考点:
- 考点1:能否正确构造图
- 考点2:基于深度优先搜索/广度优先 搜索的拓扑排序
构建图:
解题思路 1:基于广度优先搜索的拓扑排序
package com.lcz.leetcode;// 课程表IIimport java.util.*;public class Leetcode210 { class Solution { //构造图 List> edges; // 存储入度结点 int[] indeg; // 存储结果 int[] res; // 存储结果的索引 int index; public int[] findOrder(int numCourses, int[][] prerequisites) { // 对上述初始化 edges = new ArrayList >(); for(int i=0;i ()); } indeg = new int[numCourses]; res = new int[numCourses]; index = 0; // 构建图 for(int[] info:prerequisites) { edges.get(info[1]).add(info[0]); res[info[0]]++; } // 广度优先搜索 队列 Queue queue = new LinkedList (); // 将入度为0的结点都放入队列中 for(int i=0;i
基于深度优先搜索的拓扑排序
class Solution { // 存储有向图 List
> edges; // 标记每个节点的状态:0=未搜索,1=搜索中,2=已完成 int[] visited; // 用数组来模拟栈,下标 n-1 为栈底,0 为栈顶 int[] result; // 判断有向图中是否有环 boolean valid = true; // 栈下标 int index; public int[] findOrder(int numCourses, int[][] prerequisites) { edges = new ArrayList
>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList ()); } visited = new int[numCourses]; result = new int[numCourses]; index = numCourses - 1; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); } // 每次挑选一个「未搜索」的节点,开始进行深度优先搜索 for (int i = 0; i < numCourses && valid; ++i) { if (visited[i] == 0) { dfs(i); } } if (!valid) { return new int[0]; } // 如果没有环,那么就有拓扑排序 return result; } public void dfs(int u) { // 将节点标记为「搜索中」 visited[u] = 1; // 搜索其相邻节点 // 只要发现有环,立刻停止搜索 for (int v: edges.get(u)) { // 如果「未搜索」那么搜索相邻节点 if (visited[v] == 0) { dfs(v); if (!valid) { return; } } // 如果「搜索中」说明找到了环 else if (visited[v] == 1) { valid = false; return; } } // 将节点标记为「已完成」 visited[u] = 2; // 将节点入栈 result[index--] = u; }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/110916615 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月15日 18时00分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29
Java LinkedHashMap
2019-04-29
JPA 多线程同时对一条数据进行Update的问题
2019-04-29
JPA 多线程对数据进行更新,Update和Insert同时存在的问题
2019-04-29
Java 高性能队列Disruptor
2019-04-29
SpringBoot 使用https
2019-04-29
Java 读写锁
2019-04-29
JVM Minor GC、Full GC和Major GC
2019-04-29
SpringBoot @Scheduled 执行两次的问题
2019-04-29
tomcat配置JVM
2019-04-29
Ubuntu软件安装&卸载
2019-04-29
面试笔试易错知识点Java篇八
2019-04-29
弹性事务框架ETF4J——面向Java微服务的交易最终一致性解决方案
2019-04-29
【Scala 教程】Scala 条件与循环语句
2019-04-29
【Scala 教程】Scala 集合类型
2019-04-29
JAVA 线程同步机制 synchronized
2019-04-29
MySQL 安装教程(无脑版)
2019-04-29