`

Leetcode - Course Schedule

 
阅读更多
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-leetcode题解之207-Course-Schedule.py

    python python_leetcode题解之207_Course_Schedule.py

    java-leetcode题解之Course Schedule III.java

    java java_leetcode题解之Course Schedule III.java

    javalruleetcode-LeetCode-Solutions:LeetCode-解决方案

    Course Schedule II" 和 "146. LRU Cache"。这些问题要求我们设计并实现一个高效的缓存机制,LRU Cache 是理想的解决方案。通过分析和解答这些题目,我们可以加深对 LRUCache 工作原理的理解,并提升 Java 编程技巧...

    lrucacheleetcode-leetcode-java:力码研究

    Course Schedule II**:这个问题可以通过模拟LRU缓存来解决,其中每个课程代表一个元素,课程的依赖关系决定了元素的使用顺序。 2. **146. LRU Cache**:这是一个直接要求实现LRU缓存的题目,是理解LRU机制的好例子...

    多线程leetcode-LeetCode:某物

    _210_CourseSchedule2_BFS_DFS_TopoLogicalSort 两个指针 _75_SortColors_twopointer _142_LinkedListCycle2_twopointer //////// 弗洛伊德循环检测 _287_FindtheDuplicateNumber_TwoPointer_Floyd _340_...

    LeetCode-Feb2021

    Java中的图通常用邻接矩阵或邻接表表示,如"Course Schedule"(课程表)。Dijkstra算法和Floyd-Warshall算法可用于求解最短路径问题。 以上就是2021年2月LeetCode的Java解题集锦所涵盖的知识点,通过这些题目,...

    LeetCode-Java

    6. **图论**:虽然LeetCode上的图问题相对较少,但依然有如"Course Schedule"这样的问题,涉及拓扑排序和深度优先搜索。 7. **设计模式**:在解决一些复杂问题时,如"Design HashMap",可能会考察到设计模式的应用...

    leetcode卡-leet-code-may-challenge:包含对MayChallenge(LeetCode)上发布的问题的解决方案。

    3. 图论:如“Course Schedule II”可能涉及拓扑排序和深度优先搜索。 4. 字符串处理:如“Valid Palindrome II”要求实现字符串的双指针法或者动态规划解决。 5. 排序与搜索:比如“Search in Rotated Sorted Array...

    LeetCode_java_leetcode_刷题_

    10. **图形与图论**:如"Course Schedule"类问题,涉及到拓扑排序的概念。 通过这个资料包,你可以按照题目列表逐一攻克,每次解决问题后,不仅要加强代码实现,还要理解解题思路,分析时间复杂度和空间复杂度,...

    javalruleetcode-leetcode:leetcode

    Course Schedule II`(课程表II)、`202. Happy Number`(快乐数)、`146. LRU Cache`(LRU 缓存机制)等。 4. **LRUCache 应用场景**: - 在数据库查询优化中,LRUCache 用于缓存最近查询过的数据,减少对数据库...

    leetcode1004-aoj:AOJ

    leetcode 1004 *LC 75problems =&gt; OK/NG =&gt; NG 表示我无法自己解决,所以我...20200123_hrd_630_course_schedule_iii NG 20200123全部/所有媒体20200123 20200123_mdm_785_is_graph_bipartite OK 20200122全部/所有媒

    LeetCode

    10. **图论**:包括图的深度优先遍历、拓扑排序、最小生成树等(如LeetCode的"Course Schedule"问题)。 11. **数据结构设计**:包括自定义栈、队列、堆等,用于满足特定需求(如LeetCode的"Design a Stack with ...

    python-leetcode面试题解之第207题课程表-题解.zip

    在LeetCode的面试题中,第207题是“课程表”(Course Schedule),这是一道涉及图论和拓扑排序的问题。它主要考察的是考生对数据结构和算法的理解,特别是对于有向无环图(DAG)的处理能力。本题解将深入探讨这个...

    leetcode:Leetcode学习代码

    例如,"Course Schedule" (题号 207) 要求找出是否存在完成所有课程的顺序。 7. **动态规划**:通过状态转移方程解决最优化问题。例如,"Unique Paths" (题号 62) 需要计算一个机器人到达目标位置的路径数量。 8. ...

    oj题.zip

    2. **207.py** - 这可能是LeetCode的207题,"Course Schedule"(课程表),涉及图论中的拓扑排序或深度优先搜索(DFS)来确定是否存在课程间的依赖关系。 3. **143.py** - 可能对应的是LeetCode的143题,"Reorder ...

    leetcode_blog

    图的问题虽然较少,但仍然重要,比如“Course Schedule”问题,涉及拓扑排序,帮助我们理解图的节点依赖关系。 哈希表是解决很多问题的利器,如“First Unique Character in a String”,可以利用哈希表记录字符...

    Facebook 最新面试题总结

    Course Schedule(课程表)**: - 需要判断是否可以根据给定的课程要求,完成所有课程的学习。 3. **LeetCode 674. Longest Continuous Increasing Subsequence(最长连续递增子序列)**: - 求出一个数组中最长...

    lrucacheleetcode-Algorithms:个人学习笔记

    Course Schedule II`、`212. Word Search II`以及著名的`146. LRU Cache`。这些问题可以帮助理解LRU的工作原理,并锻炼实现LRU缓存的数据结构和算法能力。 6. **应用**: - LRU缓存广泛应用于数据库系统、操作...

Global site tag (gtag.js) - Google Analytics