資料結構
網路
關係資料庫管理系統 (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 次瀏覽
