力扣课程表1-3 java实现

三道课程表题，前两道与拓扑排序相关，第三道题与优先队列的贪心算法有关。

课程表Ⅰ

思路
拓扑排序的话可以考虑用广度优先搜索的方法，判断图是否有环。
一门课有先修课程，说明这门课是有入度的，可以从这一点入手。
构造邻接表来存储图，利用入度矩阵存储每个节点的入度，将入度为0的节点一次入队，然后遍历，减少其对应端点的入度，最后判断是否全部入队。

public boolean canFinish(int numCourses, int[][] prerequisites) {
        int []degrees=new int[numCourses];//入度矩阵
        List<List<Integer>> graph=new ArrayList<>();
        Queue<Integer> queue=new LinkedList<>();
   		//初始化图
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }
        for(int []temp:prerequisites){
            degrees[temp[0]]++;
            graph.get(temp[1]).add(temp[0]);//构建图
        }
        //入度为0的课程入队
        for(int i=0;i<numCourses;i++){
            if(degrees[i]==0)
                queue.add(i);
        }
        while(!queue.isEmpty()){
            int temp=queue.poll();
            numCourses--;
            for(int cur:graph.get(temp)){
                if(--degrees[cur]==0)
                    queue.add(cur);
            }
        }
        return numCourses==0;
    }

课程表Ⅱ

思路
这里的思路与上一题类似，因为要输出课程顺序，所以多了一个存储步骤。

public int[] findOrder(int numCourses, int[][] prerequisites) {
		int []res=new int[numCourses];//存储学习顺序
        int []degrees=new int[numCourses];
        List<List<Integer>> graph=new ArrayList<>();
        Queue<Integer> queue =new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }
        for(int [] temp:prerequisites){
            degrees[temp[0]]++;
            graph.get(temp[1]).add(temp[0]);
        }
        for(int i=0;i<numCourses;i++){
            if(degrees[i]==0)
                queue.add(i);
        }
        int count=0;
        while(!queue.isEmpty()){
            int temp=queue.poll();
            res[count++]=temp;
            for(int cur:graph.get(temp)){
                if(--degrees[cur]==0)
                    queue.add(cur);
            }
        }
        return count==numCourses?res:new int[]{};
    }

PS：这两题还有一个方式不使用ArrayList实现，但是实现代价却会更高，主要是在修改课程入度的时候做了变化，在这里贴出主要代码供大家参考。

			// 修改节点入度
            for(int[] edge : prerequisites) {
                if (edge[1] == temp) {
                    degrees[edge[0]]--;
                    if (degrees[edge[0]] == 0) {
                        queue.offer(edge[0]);
                    }
                }
            }

课程表Ⅲ

思路
这一题要求得出最多能修几门课程，应该能想到贪心算法的思想，这里有一个课程耗费跟课程结束时间，不过优先队列我确实没有首先想到，看了思路之后才发现优先队列+贪心算法的结合已经很可了…（看到有基于贪心算法的堆排序实现的，好像效果也很不错）

public int scheduleCourse(int[][] courses) {
        //根据课程结束时间升序排列
        Arrays.sort(courses,(a,b) -> (a[1]-b[1]));
        //课程用时的大根优先级队列
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> (b-a));
        int time = 0;
        for (int[] temp: courses) {
            //如果不能学习此课程，因为此课程结束时间比之前所有的都晚，存在两种情况：
            //1.此课程用时比之前某个课程少：则学习此课程，放弃之前用时最长的课程
            //2.此课程用时比之前所有课程多：则不学习此课程，可以理解为学习此课程，同时放弃之前用时最长的课程
            if (time + temp[0] <= temp[1]) {
                queue.offer(temp[0]);
                time += temp[0];
            } else if (!queue.isEmpty() && queue.peek() > temp[0]) {
                time += temp[0] - queue.poll();
                queue.offer(temp[0]);
            }
        }
        return queue.size();
    }