分类信息建站系统,怎么快速推广自己的产品,网站的横幅怎么做,php网站开发速成课程表
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i] [ai, bi] #xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。…课程表
你这个学期必须选修 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 。这是可能的。
解题思路 这个问题可以转化为判断有向图中是否存在环的问题如果存在环 则说明存在课程之间的循环依赖无法完成所有课程的学习 如果不存在环则说明不存在循环依赖可以完成所有课程的学习。 1、使用拓扑排序来判断是否存在环即是否可以完成所有课程的学习。 2、使用邻接表来表示课程之间的先修关系。 3、统计每门课程的入度入度为0表示没有先修课程。 4、将入度为0的课程加入队列并从队列中依次弹出课程将其后继课程的入度减1。 5、如果存在环即存在入度为0的课程无法全部弹出则说明无法完成所有课程的学习返回false否则返回true。
Java实现
广度优先搜索BFS实现
public class CourseSchedule {public boolean canFinish(int numCourses, int[][] prerequisites) {// 构建有向图和入度数组MapInteger, ListInteger graph new HashMap();int[] indegree new int[numCourses];for (int[] prereq : prerequisites) {int course prereq[0];int prereqCourse prereq[1];graph.putIfAbsent(prereqCourse, new ArrayList());graph.get(prereqCourse).add(course);indegree[course];}// 将入度为 0 的节点加入队列中QueueInteger queue new LinkedList();for (int i 0; i numCourses; i) {if (indegree[i] 0) {queue.offer(i);}}// 使用广度优先搜索进行拓扑排序int visited 0;while (!queue.isEmpty()) {int course queue.poll();visited;ListInteger neighbors graph.getOrDefault(course, new ArrayList());for (int neighbor : neighbors) {indegree[neighbor]--;if (indegree[neighbor] 0) {queue.offer(neighbor);}}}return visited numCourses;}public static void main(String[] args) {CourseSchedule scheduler new CourseSchedule();int numCourses 4;
// int[][] prerequisites {{1, 0}, {2, 1}, {3, 2}, {3, 1}};int[][] prerequisites {{1, 0}, {2, 1}, {3, 2}, {1, 3}};System.out.println(scheduler.canFinish(numCourses, prerequisites));}
}
时间空间复杂度 时间复杂度O(V E)其中 V 表示课程数量E 表示先修课程的数量因为需要构建邻接表和统计入度以及进行BFS拓扑排序。 空间复杂度O(V E)其中 V 表示课程数量E 表示先修课程的数量因为需要存储邻接表和入度数组。
