資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python課程安排
假設我們總共有numCourses門課程需要學習，編號從0到numCourses-1。一些課程可能有先修課程，例如，要學習課程0，我們必須先學習課程1，這用一對數字表示：[0,1]。假設提供了課程總數和先修課程對列表，我們需要檢查是否可以完成所有課程？
因此，如果輸入是這樣的——numCourses = 2， prerequisites = [[1, 0]]，則結果為true，因為總共有2門課程需要學習。要學習課程1，我們必須先完成課程0。所以這是可能的。
為了解決這個問題，我們將遵循以下步驟：
在主方法中，它將接收numCourses和prerequisites：這將起作用——
如果prerequisites沒有條目，則返回true
建立一個名為visited的陣列，用0填充它，其範圍與numCourses相同
adj_list := 使用prerequisites建立一個圖
對於範圍從0到numCourses的i
如果visited[i]為false，則
如果圖中訪問過的節點之間沒有迴圈，則返回false
返回true
示例
讓我們來看下面的實現，以便更好地理解：
class Solution(object):
def canFinish(self, numCourses, prerequisites):
if len(prerequisites) == 0:
return True
visited = [0 for i in range(numCourses)]
adj_list = self.make_graph(prerequisites)
for i in range(numCourses):
if not visited[i]:
if not self.cycle(adj_list,visited,i):
return False
return True
def cycle(self,adj_list,visited,current_node = 0):
if visited[current_node] ==-1:
return False
if visited[current_node] == 1:
return True
visited[current_node] = -1
if(current_node in adj_list):
for i in adj_list[current_node]:
if not self.cycle(adj_list,visited,i):
return False
visited[current_node] = 1
return True
def make_graph(self,array):
adj_list = {}
for i in array:
if i[1] in adj_list:
adj_list[i[1]].append(i[0])
else:
adj_list[i[1]] = [i[0]]
return adj_list
ob = Solution()
print(ob.canFinish(2, [[1,0]]))輸入
2 [[1,0]]
輸出
true
更新於：2020年4月29日
889 次瀏覽
廣告