https://leetcode.com/problems/course-schedule/
[分析] 典型的拓扑排序应用。先根据课程的先修关系构造一个graph,graph中的节点数==课程数,先修关系pair代表graph中的一条边,注意测试case中先修关系有重复,因此仅当创建新边时才更新相应节点的indegree。
public class Solution {
// method 2: 二维数组表示有向图
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)
return true;
// 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 m = prerequisites.length;
for (int i = 0; i < m; i++) {
if (graph.get(prerequisites[i][0]).add(prerequisites[i][1]))
indegree[prerequisites[i][1]]++;
}
// check
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()) {
counter++;
int curr = queue.poll();
for (int w : graph.get(curr)) {
if (--indegree[w] == 0) queue.offer(w);
}
}
return counter == numCourses;
}
// method 1
class Vertex {
int value;
int indegree;
HashSet<Vertex> adjacent;
public Vertex(int val) {
this.value = val;
indegree = 0;
adjacent = new HashSet<Vertex>();
}
}
public boolean canFinish1(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)
return true;
HashMap<Integer, Vertex> graph = buildGraph(numCourses, prerequisites);
LinkedList<Vertex> queue = new LinkedList<Vertex>();
for(Vertex node : graph.values()) {
if (node.indegree == 0)
queue.offer(node);
}
int counter = 0;
while (!queue.isEmpty()) {
Vertex node = queue.poll();
counter++;
for (Vertex w : node.adjacent) {
w.indegree--;
if (w.indegree == 0) queue.offer(w);
}
}
return counter == graph.size();
}
private HashMap<Integer, Vertex> buildGraph(int numCourses, int[][] prerequisites) {
HashMap<Integer, Vertex> graph = new HashMap<Integer, Vertex>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new Vertex(i));
}
int m = prerequisites.length;
for (int i = 0; i < m; i++) {
if(graph.get(prerequisites[i][0]).adjacent.add(graph.get(prerequisites[i][1]))) {
graph.get(prerequisites[i][1]).indegree++;
}
}
return graph;
}
}
分享到:
相关推荐
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",可能会考察到设计模式的应用...
3. 图论:如“Course Schedule II”可能涉及拓扑排序和深度优先搜索。 4. 字符串处理:如“Valid Palindrome II”要求实现字符串的双指针法或者动态规划解决。 5. 排序与搜索:比如“Search in Rotated Sorted Array...
10. **图形与图论**:如"Course Schedule"类问题,涉及到拓扑排序的概念。 通过这个资料包,你可以按照题目列表逐一攻克,每次解决问题后,不仅要加强代码实现,还要理解解题思路,分析时间复杂度和空间复杂度,...
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全部/所有媒
10. **图论**:包括图的深度优先遍历、拓扑排序、最小生成树等(如LeetCode的"Course Schedule"问题)。 11. **数据结构设计**:包括自定义栈、队列、堆等,用于满足特定需求(如LeetCode的"Design a Stack with ...
在LeetCode的面试题中,第207题是“课程表”(Course Schedule),这是一道涉及图论和拓扑排序的问题。它主要考察的是考生对数据结构和算法的理解,特别是对于有向无环图(DAG)的处理能力。本题解将深入探讨这个...
例如,"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缓存广泛应用于数据库系统、操作...