Dx's Tech Notes

3._课程表

5 min read

  • 3.1

    • graph 代表邻接矩阵，用 List<List<>> 来作“二维数组 ，0 的位置作入度+1
    • 在 while 中，取出下一个节点用 graph。get（b），取出 next 也就是下个节点，-1，判断是否入队列

  • 2.12

    • 用 List<List<>> 来作“二维数组”。用单独入度数组记录，用q 存入度为 0 的的课，并扫描后接的课。用 nums 记录全局已经学过的课

  • 1.30

    • 用 List<List<Integer>> 来实现邻接矩阵[1,0]先学 0 课程才能学 1 课程，在初始入度时，0 做头结点，1 接在后面
    • 之后用队列存储可以被学习的课程，然后得出当前课程后跟的节点，判断是否可学以及再次存入队列
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 初始化图：必须用 numCourses
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < numCourses; i++) { // 【修正1】
            graph.add(new ArrayList<>());
        }
 
        int[] inDegree = new int[numCourses];
 
        // 2. 建图
        for(int[] course : prerequisites){
            int a = course[0];
            int b = course[1];
            graph.get(b).add(a);
            inDegree[a]++;
        }
 
        int number = 0;
        Queue<Integer> q = new LinkedList<>();
 
        // 3. 找第一批入度为 0 的课：必须遍历所有课程
        for(int i = 0; i < numCourses; i++){ // 【修正2】
            if(inDegree[i] == 0) {
                q.offer(i); // 【修正3：放入课程ID i，而不是值 0】
            }
        }
 
        while(!q.isEmpty()){
            int curr = q.poll(); // 拿出来的是“课程ID”
            number++;
            
            for(int next : graph.get(curr)){
                inDegree[next]--;
                if(inDegree[next] == 0) {
                    q.offer(next); // 【修正4：放入课程ID next】
                }
            }
        }
        
        return number == numCourses;
    }
}
  • 11.14
    • 非常有难度,主要在于a与b的关系,放入邻接矩阵是b放在头,a放在b的后面,因为从a开始遍历到后,b肯定能学,b学完才能a学(这里在二次填充邻接表时用到,同时更新入度)
    • 邻接矩阵的声明与填充
    • 每门课的入度!如果入度为0,代表无牵无挂,可以学习
    • 类似烂橘子,从入度为0的开始插入队列,用cur指针往后(消入度)腐烂,cur指针就是弹出队列的课程!
    • 在腐烂之前,依照题意需要声明已学习参数,看最后学习完了没

学 A → 才能学 C(这里A等于题目的bi) 学 B → 才能学 C 学 C → 才能学 D 学 C → 才能学 E 0 → 2 1 → 2 2 → 3 2 → 4

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
​
        //构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<numCourses;i++) graph.add(new ArrayList<>());
​
        int[] indegree = new int[numCourses];//每门课的入度数
​
        for(int[] pre:prerequisites){
            int a=pre[0],b = pre[1];
            graph.get(b).add(a);//b-》a
            indegree[a]++;// a的入度➕1
        }
 
        
      //   for(int i=0;i<prerequisites.length;i++){
      //      gragh.get(prerequisites[i][1]).add(prerequisites[i][0]);
      //      indegree[prerequisites[i][0]]++;
      //  }
        
​
        //队列存放当前可以学习的课程(入度为0)
        Queue<Integer>q = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) q.offer(i);
        }
​
        int learned=0;
        while(!q.isEmpty()){
            int cur = q.poll();
            learned++;
            for(int next:graph.get(cur)){
                indegree[next]--; //学完当前课,后继课入度-1
                if(indegree[next]==0) q.offer(next);//新课可学,入队
            }
        }
        return learned==numCourses;
​
    }
}

Graph View

Backlinks