美文网首页
Leetcode 207 课程表

Leetcode 207 课程表

作者: 尹学姐 | 来源:发表于2023-03-27 21:32 被阅读0次

    题目要求

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

    在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

    例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
    请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

    示例 1:

    输入:numCourses = 2, prerequisites = [[1,0]]
    输出:true
    解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

    示例 2:

    输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
    输出:false
    解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

    解题思路

    这道题是一道典型的拓扑排序的题。

    拓扑排序是图论中的理论,主要流程如下:

    • 首先构造邻接表和入度
    • 遍历入度为0的节点,同时将依赖他们的节点入度-1
    • 再次遍历此时入度为0的节点,重复步骤2
    • 直到没有入度为0的节点

    几个特点:

    • 拓扑排序只能处理有向无环图
    • 如果有环,则无法遍历完所有节点

    Java代码

    class Solution {
        // 构造一个数据结构,记录所有的邻接节点
        class Course{
            int id;
            Set<Course> children;
            int in;
    
            public Course(int id){
                this.id = id;
                this.children = new HashSet<>();
            }
        }
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Course[] courses = new Course[numCourses];
            for(int i = 0; i < numCourses; i++){
                courses[i] = new Course(i);
            }›
            for(int i = 0; i < prerequisites.length; i++){
                int[] require = prerequisites[i];
                courses[require[0]].children.add(courses[require[1]]);
                courses[require[1]].in++;
            }
            // 通过队列来遍历
            Queue<Course> queue = new LinkedList<>();
            for(int i = 0; i < numCourses; i++){
                // 将入度为0的节点加入队列
                if(courses[i].in == 0) queue.offer(courses[i]);
            }
            int size = 0;
            while(!queue.isEmpty()){
                Course course = queue.poll();
                size++;
                // 修改当前节点所有的邻接节点的入度
                for(Course child : course.children){
                    child.in--;
                    // 如果邻接节点入度为0,加入队列
                    if(child.in == 0){
                        queue.offer(child);
                    }
                }
            }
            // 如果遍历完所有的节点,则表示无环
            return size == numCourses && queue.isEmpty();
        }
    }
    

    总结

    Grind75里面的题目,通常都是挑选每一类里面最典型的题目,基本上一眼就能看出需要用什么算法。

    拓扑排序是一种非常常见的算法,有一套规范的写法,必须掌握。

    相关文章

      网友评论

          本文标题:Leetcode 207 课程表

          本文链接:https://www.haomeiwen.com/subject/vxazrdtx.html