流媒体视频网站建设,刷手机网站关键词,苏州网站建设流程,58黄页网推广公司207. 课程表
解题思路 首先构建了一个 inDegree 哈希表#xff0c;用于存储每门课程的入度#xff0c;即有多少课程依赖当前课程。 构建了一个 adj 哈希表#xff0c;用于存储每门课程所依赖的其他课程。这个结构可以理解为一个邻接表#xff0c;对于每门课程#xff0c…207. 课程表
解题思路 首先构建了一个 inDegree 哈希表用于存储每门课程的入度即有多少课程依赖当前课程。 构建了一个 adj 哈希表用于存储每门课程所依赖的其他课程。这个结构可以理解为一个邻接表对于每门课程存储了其所有的前置课程。 根据给定的课程依赖关系数组 prerequisites更新了每门课程的入度和依赖关系。 初始化一个队列 q将所有入度为 0 的课程加入队列。这些课程是没有任何先修课程的课程可以直接学习。 开始一个循环每次从队列中取出一门课程表示这门课程被选择学习。然后遍历其邻接表中的课程将这些课程的入度减 1并将入度减为 0 的课程加入队列表示这些课程可以被学习了。 最后遍历所有课程的入度如果存在入度不为 0 的课程说明存在环路直接返回 false表示无法完成所有课程的学习否则返回 true表示能够完成所有课程的学习。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 先让入度为0 的课入队// 然后逐个出队 出队的课代表被选择然后减小相关课程的入度// 如果相关课的入度为0 安排出队// 课程号和对应的入度MapInteger,Integer inDegree new HashMap();// 将所有的课程先放入for(int i 0; i numCourses; i){inDegree.put(i,0);}// 依赖关系 计算每一门课程所依赖的前面的课程// cur 依赖pre cur1依赖 pre 那么 pre ,(cur,cur1)MapInteger,ListInteger adj new HashMap();// 初始化入度和依赖的关系for(int[] relate: prerequisites){// 想要学cur 必须先完成pre 也就是cur 依赖pre pre指向cur 作为cur的一个入度int cur relate[0];int pre relate[1];// 更新入度inDegree.put(cur,inDegree.get(cur) 1);// 入度 1if(!adj.containsKey(pre)){// 如果不存在依赖关系 先初始化adj.put(pre,new ArrayList());}adj.get(pre).add(cur);}QueueInteger q new LinkedList();// 将所有入度为0 的全部入队for(int key:inDegree.keySet()){if(inDegree.get(key) 0){q.offer(key);}}// 取出一个节点 对应学习这门课程// 遍历当前邻接表 更新其入度 更新之后 查看入度 如果为0 加入到队列while(!q.isEmpty()){int cur q.poll();// 取出当前课程// 查看当前课程是否存在邻接表if(!adj.containsKey(cur)){continue;}ListInteger successorList adj.get(cur);// 取出它的邻接表// 遍历所有的需要依赖当前课程cur 的所有课程for(int k: successorList){// 依赖cur的课程 入度减小1inDegree.put(k,inDegree.get(k) - 1);// 入度减小1// 当依赖cur的课程 入度减小为1的时候 直接入队if(inDegree.get(k) 0){q.offer(k);}}}// 遍历队列 如果还有课程的入度不为0 说明存在环路 直接falsefor(int key:inDegree.keySet()){if(inDegree.get(key) ! 0){return false;}}return true;}
}
