LeetCode (Course Schedule I, II, III, IV)

1. Course Schedule(Medium)

`    # Time O(E+V) Space O(E+V), runtime = 212 ms    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:                if not prerequisites: return True                pre_course_dict = collections.defaultdict(list)        cc_dict = collections.defaultdict(list)        for c, p in prerequisites:            pre_course_dict[p].append(c)            cc_dict[c].append(p)                result = []        in_progress = collections.deque([])        # find the node donnot have pre requests        vs = []        for v in pre_course_dict.values():            vs += v        for k in pre_course_dict.keys():            if k not in vs:                in_progress.append(k)                 while in_progress:            pre = in_progress.popleft()            result.append(pre)            for course in pre_course_dict[pre]:                cc_dict[course].remove(pre)                if not cc_dict[course]:                    in_progress.append(course)        return len(result) == len(pre_course_dict)`

2. Course Schedule II(Medium):

`    # Time O(V+E) Space O(V+E)    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:                    pre_dict = collections.defaultdict(list)        course_dict = collections.defaultdict(list)        for [course, pre] in prerequisites:            pre_dict[pre].append(course)            course_dict[course].append(pre)                    todo = collections.deque([])        results = []        for i in range(numCourses):            if i not in course_dict:                todo.append(i)while todo:            c1 = todo.popleft()            results.append(c1)                        if c1 in pre_dict:                for c2 in pre_dict[c1]:                    course_dict[c2].remove(c1)                    if course_dict[c2] == []:                        todo.append(c2)                        if len(results) < len(course_dict):                    return []                  return results`

4. Course Schedule IV(Medium):

Software Engineer

More from Jing Dong

Software Engineer