項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [207] Course Schedule 個人解法筆記

題目出處

207. Course Schedule

難度

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)MatrixPython
⭐ Binary Serach 相關題型 ⭐
33Search in Rotated Sorted ArrayBinary SerachArrayPython #重