This is the fifth day of my participation in the First Challenge 2022

The title

210. Curriculum II

Now you have a total of numCourses to select, denoting 0 to numcourses-1. For example, for example, system member for office system [I] = system member for OFFICE system [AI, bi]

  • For example, want to take a course0You need to complete the course first1, we use a match to represent:[0, 1] 。

Returns the order in which you studied in order to complete all the lessons. There could be multiple correct orders, and you just have to return any one of them. If it is not possible to complete all lessons, return an empty array.

 

Example 1:

Input: numCourses = 2, resident = [[1,0]] output: [0,1] To take course 1, you need to complete course 0 first. Therefore, the correct course order is [0,1].Copy the code

Example 2:

Input: numCourses = 4, resident = [[1,0],[2,0],[3,1]] To take course 3, you should complete course 1 and Course 2 first. And both course 1 and course 2 should come after course 0. Therefore, a correct order of lessons is [0,1,2,3]. Another correct order is [0,2,1,3].Copy the code

Example 3:

Input: numCourses = 1, Resident = [] output: [0]Copy the code

 

Tip:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai ! = bi
  • all[ai, bi] Each other is not the same

Train of thought

This topic is subject to leetCode 207 together with what we did last time. Schedule is a sibling topic. If you understand the previous article, then this topic is basically not difficult. Select * from numCourses where numCourses = numCourses and result.length = numCourses.

implementation

/ * * *@param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}* /
var findOrder = function(numCourses, prerequisites) {
    let list = new Array(numCourses).fill(0);
    let map = new Map(a);// Establish a topology relationship
    for (let i = 0; i < prerequisites.length; i++) {
        const [ a, b ] = prerequisites[i];
        list[a]++;
        map.set(b, (map.get(b) || []).concat([ a ]));
    }

    // Record the lessons completed
    let doneList = [];
    let result = [];
    for (let i = 0; i < numCourses; i++) {
        if (list[i] === 0) { doneList.push(i); result.push(i); }}while (doneList.length) {
        // Go one by one to the radio station to inform all the relevant partners
        const cur = doneList.shift();
        const temp = map.get(cur) || [];

        for (let i = 0; i < temp.length; i++) {
            list[temp[i]]--;
            if (list[temp[i]] === 0) { doneList.push(temp[i]); result.push(temp[i]); }}}return result.length === numCourses ? result : [];
};
Copy the code

If you want to improve performance, you can change the shift in the while loop to pop, because shift removes an element from the front, causing all subsequent elements to move one place forward, while POP removes the last element directly and has no effect on the previous elements. However, I still choose to use Shift, so that the situation of first in, first out can be satisfied. If the person in front of the queue is cut by the person behind, I think it will be very upset.

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.