解析
207. Course Schedule
-
base case
- case 1：如果某节点已经在 pathNodes 中了，则返回 False
- case 2：如果某节点没有 prerequisites，则直接返回 True
-
用一个 set （
pathNodes）记录已经当前路径已经访问过的节点- 如果有一个节点被访问了多次，说明有环，则说明课程无法被完成
-
递归的访问一个节点的所有 prerequisite
-
当处理完（学完）该节点的所有 prerequisite 后，
- 把该节点需要的prerequisite 置为 []（可以理解为该节点没有依赖项了），
- 然后把该节点从 pathNodes 中移除
- 返回 True
-
# DFS + hashmap - myself
# time: O(course + prerequisites) # because every course will be accessed up to two times and every dependency edge will be accessed once
def canFinish(self, numCourses, prerequisites):
# {1: [0]} means that course 1 depends on course 0 (i.e. do course 0 first, and then course 1)
prerequisiteMap = {} # course -> prerequisiteCourses
for course, prerequisite in prerequisites:
if course not in prerequisiteMap:
prerequisiteMap[course] = []
prerequisiteMap[course].append(prerequisite)
# To store all visited courses along the current DFS path to detect a circle
pathNodes = set()
# dfs 返回当前 c 是否可以被完成
def dfs(c):
if c in pathNodes:
# Detected a circle (means this course has been visited), and thus cannot finish all courses
return False
if not prerequisiteMap.get(c, []):
# Means this course doesn't have prerequisites, and hence can be completed
return True
pathNodes.add(c)
for pre in prerequisiteMap[c]:
if not dfs(pre):
return False
pathNodes.remove(c) # 移除该逻辑会出错，edge case: [[3,1],[1,4],[3,2],[2,4]] got a wrong result
del prerequisiteMap[c] # 因为此时 c 的 prerequisites 都学完了，可以当做 c 没有 prerequisites，这样就可以剪枝了（注释这一行不影响最终结果）
return True
# 不能随机选一个节点，而是要 for loop，因为 1 -> 2, 3 -> 4的 case
for course in range(numCourses):
if not dfs(course):
return False
return True
# BFS TODO
# Topological Sort (Kahn's Algorithm) - todo
ref
210. Course Schedule II
- base case
- case 1：如果某节点已经在 pathNodes 中了，则返回 False
- case 2：如果某节点没有 prerequisites，则把其加入 res 和 resSet，并返回 True
- case 3：如果某节点已经在 resSet 中了（说明之前已经学过了），则直接返回 True
- 用一个 set （
pathNodes）记录已经当前路径已经访问过的节点- 如果有一个节点被访问了多次，说明有环，则说明所有课程无法被完成
- 递归的访问一个节点的所有 prerequisite
- 当处理完（学完）该节点的所有 prerequisite 后，
- 把该节点需要的prerequisite 置为 []（可以理解为该节点没有依赖项了），
- 然后把该节点从 pathNodes 中移除
- 把该节点加入 res 和 resSet，并返回 True
- 当处理完（学完）该节点的所有 prerequisite 后，
# DFS + hashmap - myself
# time: O(course + prerequisites) # because every course will be accessed and every dependency edge will be accessed
# space: O(course)
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
# {1: [0]} means that course 1 depends on course 0 (i.e. do course 0 first, and then course 1)
prerequisiteMap = {} # course -> prerequisiteCourses
for course, pre in prerequisites:
if course not in prerequisiteMap:
prerequisiteMap[course] = []
prerequisiteMap[course].append(pre)
res, resSet = [], set()
# To store all visited courses along the current DFS path to detect a circle
pathNodes = set()
# dfs 返回当前 c 是否可以被完成
def dfs(c):
if c in pathNodes:
# Detected a circle (means this course has been visited), and thus cannot finish all courses
return False
if c in resSet:
return True # 如果 c 已经完成了，不需要重复完成
if not prerequisiteMap.get(c, []):
# Means this course doesn't have prerequisites, and hence can be completed
res.append(c)
resSet.add(c)
return True
pathNodes.add(c)
for pre in prerequisiteMap[c]:
if not dfs(pre):
return False
pathNodes.remove(c) # 移除该逻辑会出错，edge case: [[3,1],[1,4],[3,2],[2,4]] got a wrong result
res.append(c)
resSet.add(c)
del prerequisiteMap[c] # 因为此时 c 的 prerequisites 都学完了，可以当做 c 没有 prerequisites，这样就可以剪枝了（注释这一行不影响最终结果）
return True
# 不能随机选一个节点，而是要 for loop，因为 1 -> 2, 3 -> 4的 case
for c in range(numCourses):
if not dfs(c):
return []
return res
ref