怎么做轴承网站,做网站用买服务器码,wordpress 安装过程,宁乡建设局网站题目
你这个学期必须选修 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 。这是可能的。代码与解析
class Solution {/*** 判断课程是否能够完成** param numCourses 课程数量* param prerequisites 课程先修关系的数组* return 如果能完成所有课程返回true否则返回false*/public boolean canFinish(int numCourses, int[][] prerequisites) {// 创建图的邻接表ListListInteger list new ArrayList();for (int i 0; i numCourses; i) {list.add(new ArrayList());}// 初始化状态数组0表示未访问1表示正在访问-1表示已访问int[] state new int[numCourses];// 构建邻接表for (int[] cp : prerequisites) {list.get(cp[1]).add(cp[0]); // 记录先修课对应的后续课程}// 对每门课程进行深度优先搜索判断是否有环for (int i 0; i numCourses; i) {if (!dfs(list, state, i)) return false; // 若存在环则返回false}return true; // 不存在环返回true}/*** 深度优先搜索判断是否存在环** param list 课程的邻接表* param state 课程状态数组* param need 当前需要判断的课程* return 存在环返回false否则返回true*/public boolean dfs(ListListInteger list, int[] state, int need) {if (state[need] 1) return false; // 若当前课程正在访问中说明存在环返回falseif (state[need] -1) return true; // 若当前课程已访问过直接返回truestate[need] 1; // 标记当前课程正在访问中// 对当前课程的后续课程进行深度优先搜索for (Integer t : list.get(need)) {if (!dfs(list, state, t)) return false; // 若后续课程存在环返回false}state[need] -1; // 标记当前课程访问结束return true; // 当前课程不存在环返回true}
}
