生鲜电商网站建设,网站备案如何转移,宜昌营销型网站建设,深圳手机商城网站设计公司207. 课程表
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示如果要学习课程 ai 则 必须 先学习课程 …207. 课程表
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false。 示例 1 输入numCourses 2, prerequisites [[1,0]] 输出true 解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。 示例 2 输入numCourses 2, prerequisites [[1,0],[0,1]] 输出false 解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。 题目链接207. 课程表 使用拓扑排序的解法
class Solution {//拓扑排序解法 将有向无环图转换成线性序列public boolean canFinish(int numCourses, int[][] prerequisites) {//准备工作//1.节点的入度每次只能选入度为0的课//2.依赖这门课的后续课选当前课哪些节点的入度会被影响’//如何判断选择完所有的课//BFS结束时所有节点入度为0 或者 记录入列的节点个数等于门数则可以上完所有课程//入度数组 int[] inDegreenew int[numCourses];Arrays.fill(inDegree, 0);MapInteger, ListInteger adjacencyList new HashMap(); // 邻接表 // 初始化入度数组和邻接表 for (int[] prerequisite : prerequisites) { inDegree[prerequisite[0]]; // 计算课程的入度 if (adjacencyList.containsKey(prerequisite[1])) { // 如果课程已经在邻接表中添加依赖它的后续课程 adjacencyList.get(prerequisite[1]).add(prerequisite[0]); } else { // 如果课程不在邻接表中新建一个列表存储后续课程 ListInteger list new ArrayList(); list.add(prerequisite[0]); adjacencyList.put(prerequisite[1], list); } } QueueInteger queuenew LinkedList(); ;//度为0则入列for(int i0;iinDegree.length;i){if(inDegree[i]0){queue.offer(i);}}int count0;while (!queue.isEmpty()) { int currentCourse queue.poll(); // 出列一个课程 count; // 已选课程数加1 if (adjacencyList.containsKey(currentCourse)) { // 获取当前课程的所有后续课程 for (int nextCourse : adjacencyList.get(currentCourse)) { inDegree[nextCourse]--; // 后续课程的入度减1 if (inDegree[nextCourse] 0) { // 如果入度减为0加入队列 queue.offer(nextCourse); } } } } return count numCourses;}
}多了一个路径的记录
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int[] reslutnew int[numCourses];ArrayListInteger tmpresultnew ArrayListInteger();//存储课程的入度即指向该节点的节点QueueInteger queuenew LinkedList();int[] inDegreenew int[numCourses];Arrays.fill(inDegree, 0);//存储课程的后续节点(HashMapInteger,ListInteger)HashMapInteger,ListInteger mapnew HashMap();for(int[] prerequisite : prerequisites){inDegree[prerequisite[0]];if(!map.containsKey(prerequisite[1])){ListInteger listnew ArrayList();list.add(prerequisite[0]);map.put(prerequisite[1],list);}else{map.get(prerequisite[1]).add(prerequisite[0]);}}//找到入度为0的节点为先选课程for(int i0;iinDegree.length;i){if(inDegree[i]0){queue.offer(i);}}System.out.println(queue.size());if(queue.size()0){return new int[0];}while(!queue.isEmpty()){Integer nodequeue.poll();tmpresult.add(node);if (map.containsKey(node)) {ListInteger tmpmapmap.get(node);for(int i0;itmpmap.size();i){inDegree[tmpmap.get(i)]--;if(inDegree[tmpmap.get(i)]0){queue.offer(tmpmap.get(i));}}}}if(tmpresult.size()!numCourses){//new int[0]是空的数组return new int[0];}else{for (int i 0; i tmpresult.size(); i) {reslut[i] tmpresult.get(i);}return reslut;}}
}
