甘肃网站建设公司哪家好,wordpress自定义筛选,平邑做网站,登封网站建设添加链接描述
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool:# 思路是计算每一个课的入度#xff0c;然后使用队列进行入度为0的元素的进出# 数组#xff1a;下标是课程号#xff0c;array[下标]是这个课程的入度# 哈希…添加链接描述
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool:# 思路是计算每一个课的入度然后使用队列进行入度为0的元素的进出# 数组下标是课程号array[下标]是这个课程的入度# 哈希表key是课程号value是以这个课程号为先导课的课程列表注意是列表这里需要使用defaultdictmylist[0]*numCoursesmydictcollections.defaultdict(list)for i in prerequisites:mylist[i[0]]1mydict[i[1]].append(i[0])# 现在初始化队列myquecollections.deque()for i in range(len(mylist)):if mylist[i]0:myque.append(i)while myque:curmyque.popleft()cur_listmydict[cur]# numCourses-1if cur_list:for follcourse in cur_list:mylist[follcourse]-1if mylist[follcourse]0:myque.append(follcourse)# 验证入度数组是不是都为0如果不是0则返回falsefor i in mylist:if i !0:return Falsereturn True
思路
题目分析把先导课程和后续课程画图 看出来后续课程都是入度不为0的节点然后使用一个数组记录每一门课的入度使用一个字典defaultdict来保存一个课程的后续课程列表初始化数组和while循环使用bfs队列维护当前出队列的元素需要把它的后续课程列表拿出来并把里面每一个课程的入度减1如果课程入度为0就可以加入队列最后判断数组中的元素入度是不是都为0返回
collections.defaultdict的优势 它允许你在创建时指定一个默认值的类型当你访问一个不存在的键时它会使用这个默认值类型创建一个新的值并将其返回。这意味着你不会因为访问不存在的键而引发 KeyError。 对于本题的 mydictcollections.defaultdict(list)
这是使用普通dict需要初始化
# 创建一个普通的字典值的类型是数组
dict_with_arrays {}# 添加元素到字典中
dict_with_arrays[key1] [] # 这里使用空列表作为值的初始类型
dict_with_arrays[key1].append(1)
dict_with_arrays[key1].append(2)dict_with_arrays[key2] [3, 4, 5] # 初始化值为一个具有初始元素的列表# 输出字典中的值
print(dict_with_arrays[key1]) # 输出: [1, 2]
print(dict_with_arrays[key2]) # 输出: [3, 4, 5]
