題目出處
難度
medium
個人範例程式碼
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites: # no course
return True
return self.bfs(numCourses, prerequisites)
def bfs(self, num_courses, prerequisites):
# init
pre_courses, next_courses = self.get_table(num_courses, prerequisites)
start_courses = []
learned_course = []
for course, pre in pre_courses.items():
if not pre:
start_courses.append(course)
queue = collections.deque(start_courses)
visited = set()
while queue:
course = queue.popleft()
learned_course.append(course)
visited.add(course)
for next_course in next_courses[course]:
pre_courses[next_course].remove(course)
if not pre_courses[next_course] and next_course not in visited: # no pre-courses
queue.append(next_course)
else:
return num_courses == len(learned_course)
def get_table(self, num_courses, prerequisites):
pre_courses = {x:[] for x in range(num_courses)} # for record studied
next_courses = {x:[] for x in range(num_courses)} # for search
for course in prerequisites:
pre_courses[course[1]].append(course[0])
next_courses[course[0]].append(course[1])
return pre_courses, next_courses
算法說明
這題考的是 BFS 中的拓樸排序法,個人認為比較難的是在 graph 操作的部分,其他的概念相對來說還好。
另外處理 start_courses ,去尋找 indegree 為 0 的 node
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
如果沒有 prerequisites,則必 True (無課程或無先修課)
Boundary conditions
當 queue 為空時,如果還沒有辦法上完全部的課程,則為 False
(可能 Graph 有 loop)
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |
1091 | Shortest Path in Binary Matrix | BFS (最短路徑) | Matrix | Python | ||
⭐ Binary Serach 相關題型 ⭐ | ||||||
33 | Search in Rotated Sorted Array | Binary Serach | Array | Python | #重 |