leetcode(力扣) 207. 课程表1+2（图的构造与遍历，清晰思路，完整模拟）

2024-03-04 20:05| 来源: 网络整理| 查看: 265

文章目录题目描述思路分析完整代码

题目描述

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

思路分析

先构造图思路。假设有：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]

则构造图：在这里插入图片描述也就是说：

每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。接着选 2，导致课 4 的入度变 0。现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。

所以现在的思路就很简单了，所有入度为0的节点都是可以直接学习的课。

我们只需要先设置两个数组chudu和rudu，记录入度和出度情况。

比如对于：[[1,0],[2,0],[3,1],[3,2]] 则： chudu = [[1, 2], [3], [3], []] 即 i号课的出度指向 chudu[i] rudu = [0, 1, 1, 2] 即 i号课的入度有rudu[i]个课。

直接代码构造这俩数组：

for i in prerequisites: chudu[i[1]].append(i[0]) rudu[i[0]]+=1

然后构造一个队列，将所有入度为0的课加入。

for i in range(len(rudu)): if rudu[i] == 0: queue.append(i)

后面就简单了，比如有[1,2] ，图表示就是2->1。

此时2的入度为0，则2被加入队列中，拿出队列中的2，看看2是谁的入度显然2是1的入度，所以要将1的入度数减去1-当1的入度数为0的时候，表示1也是可以学习的课了，将1也加入到队列中。

第二道题就是课程表2，实际上和课程表1 基本一样。课程表1是计数，然后和题目所给的numCourses 做比较，在课程表2中更改一下，设置一个res答案数组，直接在count计数的位置变成记录答案数组就行了。

完整代码 ### 课程表1 class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 构造出入度列表 chudu = [[] for x in range(numCourses)] rudu = [0]*numCourses queue = [] count = 0 for i in prerequisites: # 添加依赖它的后续课 chudu[i[1]].append(i[0]) rudu[i[0]] += 1 for i in range(numCourses): if rudu[i] == 0: queue.append(i) while queue != []: for i in range(len(queue)): temp = queue.pop(0) count += 1 for x in chudu[temp]: rudu[x] -= 1 if rudu[x] == 0: queue.append(x) return count==numCourses ### 课程表2 class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: rudu = [0] * numCourses chudu = [[] for _ in range(numCourses)] queue = [] res = [] for i in prerequisites: chudu[i[1]].append(i[0]) rudu[i[0]]+=1 print(chudu,rudu) for i in range(len(rudu)): if rudu[i] == 0: queue.append(i) while queue!=[]: for i in range(len(queue)): temp = queue.pop() # temp号课已经学习了 res.append(temp) for j in chudu[temp]: # 遍历所有以temp为前置的课 rudu[j]-=1 if rudu[j] == 0: queue.append(j) return res if len(res) == numCourses else []

【本文地址】

公司简介

联系我们