网站后台密码是什么,阿里云域名注册企业邮箱,温州招聘网,备案网站电子照幕布文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述
现在你总共有 numCourses 门课需要选#xff0c;记为 0 到 numCourses - 1。给你一个数组 prerequisites #xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示在选修课程 ai 前 必须 … 文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述
现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 。
例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出[0,1]
解释总共有 2 门课程。要学习课程 1你需要先完成课程 0。因此正确的课程顺序为 [0,1] 。示例 2
输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]
输出[0,2,1,3]
解释总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。示例 3
输入numCourses 1, prerequisites []
输出[0]提示 1 numCourses 2000 0 prerequisites.length numCourses * (numCourses - 1) prerequisites[i].length 2 0 ai, bi numCourses ai ! bi 所有[ai, bi] 互不相同
二、代码
代码如下
class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) - List[int]:result []# 本题默认prerequisites中的课程一定存在于numCourses_list中nodes [i for i in range(numCourses)]indegree [0 for i in range(numCourses)]for i in range(len(prerequisites)):indegree[prerequisites[i][0]] 1print(indegree)while len(nodes) ! 0:if 0 not in indegree:return []de_index indegree.index(0)de_node nodes[de_index]result.append(de_node)for i in range(len(prerequisites)):if prerequisites[i][1] de_node:indegree[nodes.index(prerequisites[i][0])] - 1nodes.pop(de_index)indegree.pop(de_index)print(result)return result三、解题思路
本题在207. 课程表 Python的基础上要求输出具体的课程学习序列在之前使用入度表的基础上只需要将每次删除的入度为 0 的节点添加进入数组 result 中即可表示已经学习了该课程如果无法学完则直接返回一个空数组。最后如果能够学完全部课程返回之前记录的 result 数组即可。
