数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：计算涵盖所有不同课程的最小学期数
假设我们有一个数字n，表示有n门不同的课程，编号从1到n。我们还有一个名为relations的数组，其中relations[i]包含一对(prevCourse_i, nextCourse_i)，表示课程prevCourse_i和课程nextCourse_i之间的先决条件关系：因此必须先学习prevCourse_i才能学习nextCourse_i。我们还有一个参数k。在一个学期中，我们可以最多学习k门课程，只要我们在上一学期已经学习了我们正在学习的课程的所有先决条件。我们必须找到学习所有课程所需的最小学期数。
因此，如果输入如下所示：
则输出为3，因为在第一学期我们可以学习课程1和2，现在我们有资格学习课程3、4和5，所以如果我们在第二学期学习5和3或4中的任意一门，那么我们可以在下一个学期结束所有课程。所以我们总共需要3个学期
为了解决这个问题，我们将遵循以下步骤：
taken := 一个新的集合
g1 := 一个包含n个空列表的列表
g2 := 一个大小为n的新列表，并填充为0
w := 一个大小为n的新列表，并填充为0
semester := 0
对于relations中的每个x，执行以下操作：
将x[0]-1插入g1[x[1]-1]的末尾
将x[1]-1插入g2[x[0]-1]的末尾
weight := 从g1中所有项目的长度生成的新列表
对于从0到n-1的i，执行以下操作：
对于g1[i]中的每个x，执行以下操作：
w[x] := w[x]和weight[i]的最大值
当taken的大小小于n时，执行以下操作：
courses := 一个新的列表
对于从0到n-1的i，执行以下操作：
如果g1[i]为空且i不在taken中，则：
将(i, w[i])插入courses的末尾
如果courses的大小大于k，则：
courses = 根据第二个参数以降序对courses进行排序
courses := 前k个课程的列表
semester := semester + 1
对于courses中的每个x，执行以下操作：
对于g2[x[0]]中的每个y，执行以下操作：
从g1[y]中删除x[0]
g2[x[0]] := 空列表
将x[0]插入taken
返回semester
示例
让我们看看下面的实现，以便更好地理解
def solve(n, relations, k):
taken = set()
g1 = [[] for _ in range(n)]
g2 = [[] for _ in range(n)]
w = [0] * n
semester = 0
for x in relations:
g1[x[1]-1].append(x[0]-1)
g2[x[0]-1].append(x[1]-1)
weight = list(map(len, g1))
for i in range(n):
for x in g1[i]:
w[x] = max(w[x], weight[i])
while len(taken) < n:
courses = []
for i in range(n):
if (not g1[i]) and (i not in taken):
courses.append([i,w[i]])
if len(courses) > k:
courses = sorted(courses, key = lambda x:x[1],reverse=True)
courses = courses[:k]
semester += 1
for x in courses:
for y in g2[x[0]]:
g1[y].remove(x[0])
g2[x[0]] = []
taken.add(x[0])
return semester
n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))输入
6, [(1,3),(2,5),(2,4),(5,6)], 2
输出
3
302 次浏览
