Leetcode 210. Course Schedule II (Python)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order Is [0, 1].Copy the code

Note:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses – 1)
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• a_i! = b_i
• All the pairs [a_i, b_i] are distinct.

parsing

NumCourses = 0 to numcourses-1 Prerequisites Prerequisites Prerequisites prerequisites[I] = [ai, bi] For example, [0,1] means that you must take course 1 in order to take course 0.

Returns the order in which all courses were completed. If there are many valid answers, any one is returned. If not all lessons are completed, an empty array is returned.

207. Course Schedule 207. Course Schedule 207. Here with the solution to the problem solving, BFS directly principle is put into the degrees of 0 node in the queue, every time after the figure into the degree of 0 the nodes are removed, if the degree of 0 nodes have the same number of nodes and figure, because from the traverse forward will be returned after the nodes of the reverse, or directly returns an empty list.

answer

class Solution(object):
    
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        pre = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        queue = []
        result = []
        
        for x,y in prerequisites:
            pre[x].append(y)
            indegree[y] += 1
        
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
                
        while queue:
            cur = queue.pop(0)
            result.append(cur)
            for p in pre[cur]:
                indegree[p] -= 1
                if indegree[p] == 0:
                    queue.append(p)
        
        return result[::-1] if len(result) == numCourses else []
  	      
		
Copy the code

The results

Given in the linked list. Memory Usage: 10000 ms. Given in the Python online submissions for Course Schedule II.Copy the code

parsing

Of course, the results can also be returned directly according to the sequence of learning courses. You only need to change the pre in the above algorithm into the NXT below, and the result found at last is naturally the forward course order.

answer

class Solution(object):
    
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        nxt = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        queue = []
        result = []
        
        for x,y in prerequisites:
            nxt[y].append(x)
            indegree[x] += 1
        
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
                
        while queue:
            cur = queue.pop(0)
            result.append(cur)
            for p in nxt[cur]:
                indegree[p] -= 1
                if indegree[p] == 0:
                    queue.append(p)
        
        return result if len(result) == numCourses else []
        
        
      
Copy the code

The results

Given in the linked list in Python online submissions. Given in the Python online submissions for Course Schedule II.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation