【力扣100】207.课程表

添加链接描述

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:# 思路是计算每一个课的入度，然后使用队列进行入度为0的元素的进出# 数组：下标是课程号，array[下标]是这个课程的入度# 哈希表：key是课程号，value是以这个课程号为先导课的课程列表！注意是列表！这里需要使用defaultdictmylist=[0]*numCoursesmydict=collections.defaultdict(list)for i in prerequisites:mylist[i[0]]+=1mydict[i[1]].append(i[0])# 现在初始化队列myque=collections.deque()for i in range(len(mylist)):if mylist[i]==0:myque.append(i)while myque:cur=myque.popleft()cur_list=mydict[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

思路：

1. 题目分析：把先导课程和后续课程画图：
   
2. 看出来，后续课程都是入度不为0的节点
3. 然后使用一个数组，记录每一门课的入度
4. 使用一个字典defaultdict来保存一个课程的后续课程列表
5. 初始化数组和while循环，使用bfs队列维护
6. 当前出队列的元素需要把它的后续课程列表拿出来，并把里面每一个课程的入度减1，如果课程入度为0，就可以加入队列
7. 最后判断数组中的元素入度是不是都为0，返回

collections.defaultdict的优势

它允许你在创建时指定一个默认值的类型，当你访问一个不存在的键时，它会使用这个默认值类型创建一个新的值，并将其返回。这意味着你不会因为访问不存在的键而引发 KeyError。

对于本题的 mydict=collections.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]