思路:
1.记住已经可以选的课
2.然后用map记录先修课,用set做减法找到满足全部先修课的课加入可以选的课
代码:
class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: total = set([i for i in range(numCourses)]) # 暂时不能学的课 preCourses = set([item[0] for item in prerequisites]) # 目前可以学的课 now_acquire = total - preCourses if len(now_acquire) == 0: return False print(now_acquire) # 一门课程可能有多个先修课 preClassDict = defaultdict(set) for item in prerequisites: preClassDict[item[0]].add(item[1]) while True: after_acquire = copy.deepcopy(now_acquire) for myclass in preClassDict: if len(preClassDict[myclass]) != 0: preClassDict[myclass] -= now_acquire if len(preClassDict[myclass]) == 0: after_acquire.add(myclass) if len(after_acquire) == numCourses: return True if len(after_acquire) == len(now_acquire): return False else: now_acquire = copy.deepcopy(after_acquire) return False
总结:
set的使用
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)