数据结构
网络
关系数据库管理系统 (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 次浏览
广告