正文

leetcode-#207课程表（top100）

author  author  2022-12-04  360

关键词：

前言

本题为 LeetCode 前 100 高频题

我们社区陆续会将顾毅（Netflix 增长，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 206 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

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

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

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

2. 示例

示例 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 <= 10^5
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对互不相同

3. 答案

class CourseSchedule 
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool 
        var inDegrees = Array(repeating: 0, count: numCourses), fromTo = [Int: [Int]]()
        var coursesCouldTake = [Int](), queue = [Int]()

        // init graph
        for prerequisite in prerequisites 
            fromTo[prerequisite[1], default: []].append(prerequisite[0])
            inDegrees[prerequisite[0]] += 1
        

        // BFS
        for course in 0..<numCourses 
            if inDegrees[course] == 0 
                queue.append(course)
            
        

        while !queue.isEmpty 
            let currentCourse = queue.removeFirst()
            coursesCouldTake.append(currentCourse)

            guard let toCourses = fromTo[currentCourse] else 
                continue
            

            toCourses.forEach 
                inDegrees[$0] -= 1

                if inDegrees[$0] == 0 
                    queue.append($0)
                
            
        

        return coursesCouldTake.count ==

主要思想：拓扑排序，利用图的阶数和BFS 来解决问题。
时间复杂度： O(n)
空间复杂度： O(1)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

leetcode207.课程表|bfsdfs邻接表邻接矩阵(代码片段)

目录一、题目1.1题目描述1.2思路分析二、BFS+邻接矩阵2.1代码分析2.2完整代码三、BFS+邻接表3.1代码分析3.2完整代码四、DFS4.1思路分析4.1代码分析4.2完整代码一、题目1.1题目描述想看优化代码的小伙伴，可以直接看DFS的代... 查看详情

leetcode207课程表(拓扑排序，判断有向图环)(代码片段)

定义一个队列Q，把入度为0的结点入队若Q不为空，则取队首结点，删去所有从该点出发的边，并把这些边所到达结点的入度减一，若某个节点入度减为0，则将它入队反复进行如上操作，直到队列为空。（当总的入队次数大于节... 查看详情

207.课程表(代码片段)

算法记录LeetCode题目：在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出，其中prerequisites[i]=[ai,bi]，表示如果要学习课程ai则必须先学习课程bi。思路算法记录说明一、题目二、分析总结说... 查看详情

leetcode-courseschedule-207

有n个课程，输入一些二元组(x,y)表示先学习x必须先学习y，求根据输入的二元组的关系，能否修完所有课程拓扑排序：选择一个入度为0的节点，删除该节点并且删除该节点所有的指出去的边，重复这个过程，知道没有入度为0的... 查看详情

207.课程表(拓扑排序）(代码片段)

题目链接：https://leetcode-cn.com/problems/course-schedule/解题代码：classSolutionpublic:boolcanFinish(intnumCourses,vector<vector<int>>&prerequisites)vector<vector<int>&g 查看详情

leetcode207.课程表|bfsdfs邻接表邻接矩阵(代码片段)

leetcode-#206反转链表（top100）

前言本题为LeetCode前100高频题我们社区陆续会将顾毅（Netflix增长，《iOS面试之道》作者，ACE职业健身教练。）的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新到205期，我们会保持更新时间... 查看详情

207.课程表(拓扑排序）(代码片段)

题目链接：https://leetcode-cn.com/problems/course-schedule/解题代码：classSolutionpublic:boolcanFinish(intnumCourses,vector<vector<int>>&prerequisites)vector<vector<int>>edges;edges.resize(numCourses);queue<int>q;intin[100000+5]=0;for(int... 查看详情

207.课程表(拓扑排序）(代码片段)

题目地址(207.课程表)(代码片段)

题目地址(207.课程表)https://leetcode-cn.com/problems/course-schedule/题目描述你这个学期必须选修numCourses门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites给出，其中 prerequisites[i... 查看详情

leetcode刷题模版：201-210

...3.移除链表元素204.计数质数205.同构字符串206.反转链表207.课程表【未实现】208.实现Trie(前缀树)209.长度最小的子数组210.课程表II【未实现】结语简介Hello！非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ ... 查看详情

leetcode-#75颜色分类（top100）

参考技术A本题为LeetCode前100高频题我们社区陆续会将顾毅（Netflix增长黑客，《iOS面试之道》作者，ACE职业健身教练。）的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新了74期，我们会保持... 查看详情

leetcode刷题模版：201-210

leetcode207.courseschedule（拓扑排序）

题目Thereareatotalof n coursesyouhavetotake,labeledfrom 0 to n-1.Somecoursesmayhaveprerequisites,forexampletotakecourse0youhavetofirsttakecourse1,whichisexpressedasapair: [ 查看详情

leetcode207.courseschedule(代码片段)

Thereareatotalof n coursesyouhavetotake,labeledfrom 0 to n-1.Somecoursesmayhaveprerequisites,forexampletotakecourse0youhavetofirsttakecourse1,whichisexpressedasapair: [0,1]Giventhetotalnumberofcourses 查看详情

java207.课程表（#topologicalsort）.java(代码片段)

查看详情

java207.课程表（#topologicalsort）.java(代码片段)

查看详情