首页 > 其他分享 >LeetCode207——课程表

LeetCode207——课程表

时间:2023-09-09 15:46:38浏览次数:48  
标签:int numCourses 学习 prerequisites 课程 先修 课程表 LeetCode207

你这个学期必须选修 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 。这是不可能的。

 

提示:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

拓扑排序的板子题,将课程的对应关系看做有向图,通过拓扑排序判断课程的关系中是否存在环,若存在则不能完成所有课程的学习,若不存在则可以完成

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //拓扑排序

        //保存各个节点的入度
        int[] indegrees  = new int[numCourses];
        //用来存储图中节点的对应关系
        List<List<Integer>> list = new ArrayList<>();
        //定义栈来存储入度为0的节点
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i=0;i<numCourses;i++)
        {
            list.add(new ArrayList<>());
        }

        for(int i=0;i<prerequisites.length;i++)
        {
            indegrees[prerequisites[i][0]]++;
            list.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        //将入度为0的节点压入栈中
        for(int i=0;i<numCourses;i++)
        {
            if(indegrees[i] == 0)
            {
                stack.push(i);
            }
        }
        //若栈中有元素,将栈顶元素出栈,课程数对应-1,将把该元素作为前序元素的元素对应入度-1,然后再判断是否入栈,若栈为空但是还有课程剩余,则说明原关系中存在环,不能完成所有课程的学习
        while(!stack.isEmpty())
        {
            int pre = stack.pop();
            numCourses--;
            for(int num : list.get(pre))
            {
                indegrees[num]--;
                if(indegrees[num] == 0)
                {
                    stack.push(num);
                }
            }
        }

        return numCourses == 0;
    }
}

 

标签:int,numCourses,学习,prerequisites,课程,先修,课程表,LeetCode207
From: https://www.cnblogs.com/Yuansj0206/p/17689548.html

相关文章

  • LeetCode -- 207. 课程表 (拓扑排序)
     经典拓扑排序的应用,用拓扑排序的算法看看原图中是否有一个合法的拓扑序。classSolution{public:conststaticintN=2010,M=5010;inth[N],e[M],ne[M],idx;intd[N],q[N];voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[......
  • vue实现课程表
    <template><div><divclass="panel"><el-table:data="timetable":span-method="objectSpanMethod"border:header-cell-style="{background:'#d9e5fd',color:'bl......
  • SQL笔试:Student学生表,Course 课程表,Sc选课表
    tudent学生表(学号,姓名、性别、年龄、组织部门),Course课程表(编号,课程名称),Sc选课表(学号,课程编号,成绩)写一个SQL语句,查询选修了计算机原理的学生学号和姓名select学号,姓名fromStudentwhere学号in(select学号fromScwhere课程编号in(Select课程编号fromCoursewhere课程名......
  • SQL笔试:Student学生表,Course 课程表,Sc选课表
    tudent学生表(学号,姓名、性别、年龄、组织部门),Course课程表(编号,课程名称),Sc选课表(学号,课程编号,成绩)写一个SQL语句,查询选修了计算机原理的学生学号和姓名select学号,姓名fromStudentwhere学号in(select学号fromScwhere课程编号in(Select课程编号fromCoursewhere课程......
  • #yyds干货盘点# LeetCode程序员面试金典:课程表
    题目:你这个学期必须选修numCourses门课程,记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites给出,其中 prerequisites[i]=[ai,bi],表示如果要学习课程 ai则必须先学习课程 bi。例如,先修课程对 [0,1]表示:想要学习......
  • LeetCode/课程表IV
    你总共需要上numCourses门课,课程编号依次为0到numCourses-1。你会得到一个数组prerequisite,其中prerequisites[i]=[ai,bi]表示如果你想选bi课程,你必须先选ai课程。有的课会有直接的先修课程,比如如果想上课程1,你必须先上课程0,那么会以[0,1]数对的形式给......
  • 8-102-(LeetCode- 207&210) 课程表
    1.题目 读题  考查点 2.解法思路这个问题可以用图论的方法来解决,具体思路如下:将课程和先修课程看作有向图的节点和边,如果要学习课程ai,则必须先学习课程bi,表示为bi->ai。判断图中是否存在环,如果存在环,则说明有些课程无法完成,返回false;如果不存在环,则说明所有课程都......
  • 8-102-(LeetCode- 207&210) 课程表II
    1.题目读题210. 课程表II 考查点 2.解法思路 这道题的解答思路是使用拓扑排序来判断有向图是否有环,如果有环,说明无法完成所有课程,如果没有环,输出拓扑排序的结果。拓扑排序的基本思想是从有向图中选择一个没有前驱(即入度为0)的顶点并输出,然后从图中删除该顶点和所......
  • LeetCode 207. 课程表
    classSolution{public:boolcanFinish(intn,vector<vector<int>>&pre){if(pre.empty()||pre[0].empty())returntrue;vector<vector<bool>>g(n,vector<bool>(n,false));for(autoq:pre)......
  • 图-邻接表-leetcode207
    你这个学期必须选修​​numCourses​​​门课程,记为​​0​​​到​​numCourses-1​​。在选修某些课程之前需要一些先修课程。先修课程按数组​​prerequisites​​给出,其中​​prerequisites[i]=[ai,bi]​​,表示如果要学习课程​​ai​​则必须先学习课程......