课程表II – LeetCode  


难度级别 中等
算法 广度优先搜索 编码 深度优先搜索 图表 访谈 面试准备 力码 力码解决方案 拓扑排序

您必须参加n项课程(从0到n-1),其中某些课程具有先决条件。 例如:对[2,1]表示要参加课程2,您必须已经修过课程1。给定整数n,它表示课程总数和课程列表及其先决条件。 我们需要返回可以完成所有n门课程的任何顺序。 如果没有可能的答案,请返回一个空白 排列。 如果有多个答案,则返回所需的答案。

课程表II-LeetCodePin

使用案列  

输入:  4

[[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3,]

输入: 2

[[1,0]]

输出: [0,1,]

使用广度优先搜索  

课程时间表的算法II – LeetCode

  1. 初始化一个表示课程数的整数n和一个用于存储课程及其前提条件的2D数组课程。
  2. 如果课程数组为空,则打印空数组。
  3. 创建大小为n的数组pCounter来存储需要先决条件的课程。
  4. 从0移到n-1并增加pCounter [course [i] [0]]。
  5. 创建一个向量 队列 存储所有先决条件。
  6. 从0移到n-1并检查pCounter中当前索引的值是否为0,然后将当前索引添加到队列中。
  7. 初始化大小为n的数组结果。
  8. 当队列不为空时,删除队列中的最后一个元素,并将其存储在结果数组和整数c中。
  9. 创建一个内部循环,并检查课程数组中[] [1]处的值是否等于c减pCounter [course [i] [0]]。
  10. 检查pCounter [course [i] [0]]是否为0,然后在队列中添加course [i] [0]。
  11. 打印结果数组。
参见
矩阵Leetcode解决方案中的幸运数字

实施   

课程安排II的C ++程序– LeetCode

#include <bits/stdc++.h> 
using namespace std; 
  
int len = 4;

void findOrder(int n, int course[4][2]){
    if(course == NULL){
        cout<<"empty array";
    }
    
    int pCounter[n];
    for(int i=0; i<len; i++){
        pCounter[course[i][0]]++;
    }
    
    vector<int> queue;
    for(int i=0; i<n; i++){
        if(pCounter[i]==0){
            queue.push_back(i);
        }
    }
    
    int numNoPre = queue.size();
    
    int result[n];
    int j=0;
    
    while(queue.size()!=0){
        int c = 0;
        if(!queue.empty()){
            c = queue.back();
            queue.pop_back();
        }    
        result[j++]=c;
        
        for(int i=0; i<len; i++){
            if(course[i][1]==c){
                pCounter[course[i][0]]--;
                if(pCounter[course[i][0]]==0){
                    queue.push_back(course[i][0]);
                    numNoPre++;
                }
            }
        
        }
    }
    
    cout<<"[";
    for(int i=0; i<n; i++){
        cout<<result[i]<<",";
    }
    cout<<"]";
}
  
int main(){
    
    int n = 4;
        int course[4][2] = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        findOrder(n, course);
    
    return 0; 
}
[0,2,1,3,]

课程表II的Java程序– LeetCode

import java.util.*;
    
class selection{
    static int[] findOrder(int n, int[][] course) {
        if(course == null){
            throw new IllegalArgumentException("empty array");
        }
        
        int len = course.length;
        
        if(len == 0){
            int[] res = new int[n];
            for(int m=0; m<n; m++){
                res[m]=m;
            }
            return res;
        }
    
        int[] pCounter = new int[n];
        for(int i=0; i<len; i++){
            pCounter[course[i][0]]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i=0; i<n; i++){
            if(pCounter[i]==0){
                queue.add(i);
            }
        }
        
        int numNoPre = queue.size();
        
        int[] result = new int[n];
        int j=0;
        
        while(!queue.isEmpty()){
            int c = queue.remove();
            result[j++]=c;
            
            for(int i=0; i<len; i++){
                if(course[i][1]==c){
                    pCounter[course[i][0]]--;
                    if(pCounter[course[i][0]]==0){
                        queue.add(course[i][0]);
                        numNoPre++;
                    }
                }
            
            }
        }
        
        if(numNoPre==n){
            return result;
        }
        else{
            return new int[0];
        }
    }
    
    public static void main (String[] args) {
        int n = 4;
        int[][] course = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        int[] result = findOrder(n, course);
        
        System.out.print("[");
        for(int i=0; i<result.length; i++){
            System.out.print(result[i]+",");
        }
        System.out.print("]");
    }
}
[0,1,2,3,]

课程表II的复杂性分析– LeetCode  

时间复杂度

O(Q * M) Q是 向量 或包含先决条件的列表,M是行数,即给定对的数量。

空间复杂度

O(M * N) 其中,M表示行数,N表示给定课程数组中的列数。

参见
在右侧Leetcode解决方案上用最大的元素替换元素

參考資料