ToB企服应用市场:ToB评测及商务社交产业平台

标题: 力扣207.课程表 [打印本页]
作者: 盛世宏图    时间: 2024-5-20 20:22
标题: 力扣207.课程表
题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，此中 prerequisites = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false
解题思路
​        用有向图描述依赖关系

​                有向图有入度和出度的概念：
​                        如果存在一条有向边A—>B，则这条边给A增长了一个出度，给B增长了一个入度
​        每次只能选你能上的课
​                （1）每次只能选入度为0的课，由于它不依赖别的课，是当下能上的课
​                （2）假设选了0，课3的先修课少了一门，入度由2变1
​                （3）接着选1，导致课3的入度变0，课4的入度变为1
​                （4）接着选2，导致课4的入度变0
​                （5）如今，课3和课4的入度为0，继承选入度为0的课，直到选不到入度为0的课
代码
  1. class Solution {
  2.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  3.         int[] indegrees = new int[numCourses];
  4.         List<List<Integer>> adjacency = new ArrayList<>();
  5.         Queue<Integer> queue = new LinkedList<>();
  6.         for(int i = 0; i < numCourses; i++)
  7.             adjacency.add(new ArrayList<>());
  9.         for(int[] cp : prerequisites) {
  10.             indegrees[cp[0]]++;
  11.             adjacency.get(cp[1]).add(cp[0]);
  12.         }
  14.         for(int i = 0; i < numCourses; i++)
  15.             if(indegrees[i] == 0) queue.add(i);
  16.         
  17.         while(!queue.isEmpty()) {
  18.             int pre = queue.poll();
  19.             numCourses--;
  20.             for(int cur : adjacency.get(pre))
  21.                 if(--indegrees[cur] == 0) queue.add(cur);
  22.         }
  23.         return numCourses == 0;
  24.     }
  25. }
复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4