There are a total of n courses you have to take, labeled from 0 to n - 1.
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]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
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].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
[分析] 对Course Schedule的简单扩展,关键点仍然是要考虑prerequisites 中可能有重复,
因此遍历prerequisites时要注意indegree数组不要重复累加,否则会得到错误答案。
ublic class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] result = new int[numCourses];
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
for (int i = 0; i < numCourses; i++)
result[i] = i;
return result;
}
//build graph
ArrayList<HashSet<Integer>> graph = new ArrayList<HashSet<Integer>>(numCourses);
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++)
graph.add(new HashSet<Integer>());
int edges = prerequisites.length;
for (int i = 0; i < edges;i++) {
if (graph.get(prerequisites[i][1]).add(prerequisites[i][0])) //考虑prerequisites可能有重复
indegree[prerequisites[i][0]]++;
}
//search
LinkedList<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0)
queue.offer(i);
}
int counter = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
result[counter] = course;
counter++;
for (int w : graph.get(course)) {
if (--indegree[w] == 0) queue.offer(w);
}
}
if (counter == numCourses)
return result;
else
return new int[0];
}
}
分享到:
相关推荐
python python_leetcode题解之207_Course_Schedule.py
java java_leetcode题解之Course Schedule III.java
Course Schedule II" 和 "146. LRU Cache"。这些问题要求我们设计并实现一个高效的缓存机制,LRU Cache 是理想的解决方案。通过分析和解答这些题目,我们可以加深对 LRUCache 工作原理的理解,并提升 Java 编程技巧...
Course Schedule II**:这个问题可以通过模拟LRU缓存来解决,其中每个课程代表一个元素,课程的依赖关系决定了元素的使用顺序。 2. **146. LRU Cache**:这是一个直接要求实现LRU缓存的题目,是理解LRU机制的好例子...
_210_CourseSchedule2_BFS_DFS_TopoLogicalSort 两个指针 _75_SortColors_twopointer _142_LinkedListCycle2_twopointer //////// 弗洛伊德循环检测 _287_FindtheDuplicateNumber_TwoPointer_Floyd _340_...
Java中的图通常用邻接矩阵或邻接表表示,如"Course Schedule"(课程表)。Dijkstra算法和Floyd-Warshall算法可用于求解最短路径问题。 以上就是2021年2月LeetCode的Java解题集锦所涵盖的知识点,通过这些题目,...
6. **图论**:虽然LeetCode上的图问题相对较少,但依然有如"Course Schedule"这样的问题,涉及拓扑排序和深度优先搜索。 7. **设计模式**:在解决一些复杂问题时,如"Design HashMap",可能会考察到设计模式的应用...
10. **图形与图论**:如"Course Schedule"类问题,涉及到拓扑排序的概念。 通过这个资料包,你可以按照题目列表逐一攻克,每次解决问题后,不仅要加强代码实现,还要理解解题思路,分析时间复杂度和空间复杂度,...
3. 图论:如“Course Schedule II”可能涉及拓扑排序和深度优先搜索。 4. 字符串处理:如“Valid Palindrome II”要求实现字符串的双指针法或者动态规划解决。 5. 排序与搜索:比如“Search in Rotated Sorted Array...
Course Schedule II`(课程表II)、`202. Happy Number`(快乐数)、`146. LRU Cache`(LRU 缓存机制)等。 4. **LRUCache 应用场景**: - 在数据库查询优化中,LRUCache 用于缓存最近查询过的数据,减少对数据库...
leetcode 1004 *LC 75problems => OK/NG => NG 表示我无法自己解决,所以我...20200123_hrd_630_course_schedule_iii NG 20200123全部/所有媒体20200123 20200123_mdm_785_is_graph_bipartite OK 20200122全部/所有媒
在LeetCode的面试题中,第207题是“课程表”(Course Schedule),这是一道涉及图论和拓扑排序的问题。它主要考察的是考生对数据结构和算法的理解,特别是对于有向无环图(DAG)的处理能力。本题解将深入探讨这个...
10. **图论**:包括图的深度优先遍历、拓扑排序、最小生成树等(如LeetCode的"Course Schedule"问题)。 11. **数据结构设计**:包括自定义栈、队列、堆等,用于满足特定需求(如LeetCode的"Design a Stack with ...
例如,"Course Schedule" (题号 207) 要求找出是否存在完成所有课程的顺序。 7. **动态规划**:通过状态转移方程解决最优化问题。例如,"Unique Paths" (题号 62) 需要计算一个机器人到达目标位置的路径数量。 8. ...
2. **207.py** - 这可能是LeetCode的207题,"Course Schedule"(课程表),涉及图论中的拓扑排序或深度优先搜索(DFS)来确定是否存在课程间的依赖关系。 3. **143.py** - 可能对应的是LeetCode的143题,"Reorder ...
图的问题虽然较少,但仍然重要,比如“Course Schedule”问题,涉及拓扑排序,帮助我们理解图的节点依赖关系。 哈希表是解决很多问题的利器,如“First Unique Character in a String”,可以利用哈希表记录字符...
Course Schedule(课程表)**: - 需要判断是否可以根据给定的课程要求,完成所有课程的学习。 3. **LeetCode 674. Longest Continuous Increasing Subsequence(最长连续递增子序列)**: - 求出一个数组中最长...
Course Schedule II`、`212. Word Search II`以及著名的`146. LRU Cache`。这些问题可以帮助理解LRU的工作原理,并锻炼实现LRU缓存的数据结构和算法能力。 6. **应用**: - LRU缓存广泛应用于数据库系统、操作...