[LeetCode] #207. Course Schedule
題目
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
- For example, the pair
[0, 1], indicates that to take course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
直覺解
構想：
為了加快尋找 prerequisites 的速度，整理一份 prerequisites 的 dictionary 版本。沒有 prerequisites 的課程一律算成 finished 的課程。
迭代所有課程，如果 prerequisites 都 finished 的話，該課程也算是 finished，如果檢查 prerequisites 的過程變成無限循環，就 return False。
python 3 實作（失敗）：
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites:
return True
finished = {}
prerequisites_dict = {}
for _, [course, pre_requisi] in enumerate(prerequisites):
if not prerequisites_dict.get(course):
prerequisites_dict[course] = []
prerequisites_dict[course].append(pre_requisi)
for course in range(numCourses):
if prerequisites_dict.get(course) is None:
finished[course] = True
for course in range(numCourses):
if finished.get(course):
continue
stack = [] + prerequisites_dict.get(course)
checked = [course]
while(stack):
requirement = stack.pop()
if requirement in checked:
return False
checked.append(requirement)
if finished.get(requirement):
continue
stack.extend(prerequisites_dict.get(requirement))
finished[course] = True
return True
實作過程中犯過的錯誤
- 因為寫了 stack = prerequisites_dict.get(course)，結果改變 stack 的內容時，連 prerequisites_dict[course] 的內容也跟著變化了。
執行結果：
Wrong Answer
Input:
3
[[0,1],[0,2],[1,2]]
Output: false
Expected: true
錯誤發生原因：
- 檢查「 prerequisites 的過程是否變成無限循環」的地方寫得太粗糙了，只在乎「是否有同一個課程被檢查了兩次」，結果遇到一個課程有多個 prerequisites 時，把不是循環的也當成循環了。
構想：
修正的地方：如果檢查到的 prerequisites 是 finished，就不要把他放進去 checked。
優化的地方：把課程分成 finished 和 unfinished。只要檢查 unfinished 的課程就好。
自己的 python 3 實作（失敗）：
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites:
return True
finished = {}
unfinished = []
prerequisites_dict = {}
for _, [course, pre_requisi] in enumerate(prerequisites):
if not prerequisites_dict.get(course):
prerequisites_dict[course] = []
prerequisites_dict[course].append(pre_requisi)
for course in range(numCourses):
if prerequisites_dict.get(course) is None:
finished[course] = True
else:
unfinished.append(course)
for course in unfinished:
stack = [] + prerequisites_dict.get(course)
checked = [course]
while(stack):
requirement = stack.pop()
if finished.get(requirement):
continue
if requirement in checked:
return False
checked.append(requirement)
stack.extend(prerequisites_dict.get(requirement))
finished[course] = True
return True
執行結果：
Wrong Answer
Input:
7
[[1,0],[0,3],[0,2],[3,2],[2,5],[4,5],[5,6],[2,4]]
Output: false
Expected: true
錯誤發生原因：
- 修正得不夠。在一堂課有多個 prerequisites 的情況下，不只是 finished 的課程會被重複檢查，unfinished 的課程也可能會被重複檢查。但重複檢查不代表有循環。要檢查第二個 prerequisites 時，checked 需要回歸初始值。
構想：
還沒想出怎麼把 checked 在適當的時機回歸初始值。試著分 degree，但是 degree 升上去之後，不知道要在什麼時候降下來。非常暴力的替代方案：把每個課程的檢查次數上限設定為 numCourses * (numCourses - 1)，超過上限就視為發生了循環。
自己的 python 3 實作：
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites:
return True
finished = {}
unfinished = []
prerequisites_dict = {}
for course, pre_requisi in prerequisites:
if course == pre_requisi:
return False
if not prerequisites_dict.get(course):
prerequisites_dict[course] = []
prerequisites_dict[course].append(pre_requisi)
for course in range(numCourses):
if prerequisites_dict.get(course) is None:
finished[course] = True
else:
unfinished.append(course)
upper_bound = numCourses * (numCourses - 1)
for course in unfinished:
stack = [] + prerequisites_dict.get(course)
count = 0
while(stack):
if count >= upper_bound:
return False
requirement = stack.pop()
if finished.get(requirement):
continue
stack.extend(prerequisites_dict[requirement])
count += 1
finished[course] = True
return True
效能：
Runtime: 1876 ms, faster than 5.04% of Python3 online submissions for Course Schedule.
Memory Usage: 51.9 MB, less than 5.15% of Python3 online submissions for Course Schedule.
構想：
優化的地方：不用迴圈次數上限，也不分 degree 改成 stack 裡的每堂課，都自帶自己的 checked list。
自己的 python 3 實作：
為了方便對照，刪掉的地方姑且用 # 註解掉
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites:
return True
finished = {}
unfinished = []
prerequisites_dict = {}
for course, pre_requisi in prerequisites:
# if course == pre_requisi:
# return False
if not prerequisites_dict.get(course):
prerequisites_dict[course] = []
prerequisites_dict[course].append(pre_requisi)
for course in range(numCourses):
if prerequisites_dict.get(course) is None:
finished[course] = True
else:
unfinished.append(course)
for course in unfinished:
stack = []
checked = [course]
for item in prerequisites_dict[course]:
stack.append([item, checked.copy()])
while(stack):
requirement, checked = stack.pop()
if finished.get(requirement):
continue
if requirement in checked:
return False
checked.append(requirement)
for item in prerequisites_dict[requirement]:
stack.append([item, checked.copy()])
finished[course] = True
return True
效能：
Runtime: 144 ms, faster than 17.06% of Python3 online submissions for Course Schedule.
Memory Usage: 15.4 MB, less than 92.94% of Python3 online submissions for Course Schedule.
研究別人的解
來源：Python by DFS and cycle detection [w/ Graph ]
別人的 python 3 實作：
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Constant defined for course state
NOT_CHECKED, CHECKING, COMPLETED = 0, 1, 2
# -------------------------------
def has_deadlock( course )->bool:
if course_state[course] == CHECKING:
# There is a cycle(i.e., deadlock ) in prerequisites
return True
elif course_state[course] == COMPLETED:
# current course has been checked and marked as completed
return False
# update current course as checking
course_state[course] = CHECKING
# check pre_course in DFS and detect whether there is deadlock
for pre_course in requirement[course]:
if has_deadlock( pre_course ):
# deadlock is found, impossible to finish all courses
return True
# update current course as completed
course_state[course] = COMPLETED
return False
# -------------------------------
# each course maintain a list of its own prerequisites
requirement = collections.defaultdict( list )
for course, pre_course in prerequisites:
requirement[course].append( pre_course )
# each course maintain a state among {NOT_CHECKED, CHECKING, COMPLETED}
# Initial state is NOT_CHECKED
course_state = [ NOT_CHECKED for _ in range(numCourses) ]
# Launch cycle (i.e., deadlock ) detection in DFS
for course_idx in range(0, numCourses):
if has_deadlock(course_idx):
# deadlock is found, impossible to finish all courses
return False
# we can finish all course with required order
return True
效能：
Runtime: 104 ms, faster than 34.68% of Python3 online submissions for Course Schedule.
Memory Usage: 17.5 MB, less than 14.31% of Python3 online submissions for Course Schedule.
研究感想：
用遞迴，很容易就可以找到「把 status 改成 COMPLETED」的時機。
他的「course_state 是 COMPLETED」，相當於我的「課程加進 finished 裡」。他在遞迴過程中，一直都有在把課程設為 COMPLETED，所以檢查過的課程不會再重複檢查。但我的寫法，在 while 迴圈中不會把檢查過的課程加進 finished 裡，所以會造成重複檢查，計算速度比較慢。
研究別人的解
來源：Python Intuitive Solution
別人的 python 3 實作：
from collections import defaultdict, deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
degree = defaultdict(int)
graph = defaultdict(set)
q = deque()
# init the courses with 0 deg
for i in range(numCourses):
degree[i] = 0
# add 1 to degree of course that needs prereq
# build edge from prerequisite to child course (directed graph)
for pair in prerequisites:
degree[pair[0]] += 1
graph[pair[1]].add(pair[0])
# start bfs queue with all classes that dont have a prerequisite
for key, val in degree.items():
if val == 0:
q.append(key)
stack = []
while q:
curr = q.popleft()
stack.append(curr)
for child in graph[curr]:
degree[child] -= 1
if degree[child] == 0:
q.append(child)
return len(stack) == numCourses
效能：
Runtime: 92 ms, faster than 90.82% of Python3 online submissions for Course Schedule.
Memory Usage: 15.4 MB, less than 93.04% of Python3 online submissions for Course Schedule.
研究感想：
先整理出一份「某某課程需要哪些 prerequisite」的紀錄，然後把可以 finish 的 prerequisite，從紀錄上刪掉。如果某課程的 prerequisite 都被刪掉了，就代表他是可以 finish 的課程，然後把它加進去 stack 裡。（所以，放在 stack 裡的課程，意味著是可以 finish 的課程）
stack 可以改成 count，初始值是 0，發現一個可以 finish 的課程就 +1，這樣可以省一些記憶體。
我的解，以及遞迴解，一次只關心一個課程的 degree，所以不同課程，degree 的處理進度不一樣，例如我是用「每堂課自己攜帶 checked」紀錄進度。他的解，是同步關心所有課程的 degree。用他的解，就不需要額外留意每堂課 degree 的處理進度到哪裡了。
Comments
Post a Comment