滨海县建设局网站,高级seo是什么职位,恶意点击软件哪几种,不花钱的网站建设问题背景
你这个学期必须选修 n u m C o u r s e s numCourses numCourses 门课程#xff0c;记为 0 0 0 到 n u m C o u r s e s − 1 numCourses - 1 numCourses−1。 在选修某些课程之前需要一些先修课程。 先修课程按数组 p r e r e q u i s i t e s prerequisites p…问题背景
你这个学期必须选修 n u m C o u r s e s numCourses numCourses 门课程记为 0 0 0 到 n u m C o u r s e s − 1 numCourses - 1 numCourses−1。 在选修某些课程之前需要一些先修课程。 先修课程按数组 p r e r e q u i s i t e s prerequisites prerequisites 给出其中 p r e r e q u i s i t e s [ i ] [ a i , b i ] prerequisites[i] [a_i, b_i] prerequisites[i][ai,bi]表示如果要学习课程 a i a_i ai 则 必须 先学习课程 b i b_i bi。 例如先修课程对 [ 0 , 1 ] [0, 1] [0,1] 表示想要学习课程 0 0 0你需要先完成课程 1 1 1。 请你判断是否可能完成所有课程的学习如果可以返回 t r u e true true否则返回 f a l s e false false。
数据约束 1 ≤ n u m C o u r s e s ≤ 2000 1 \le numCourses \le 2000 1≤numCourses≤2000 0 ≤ p r e r e q u i s i t e s . l e n g t h ≤ 5000 0 \le prerequisites.length \le 5000 0≤prerequisites.length≤5000 p r e r e q u i s i t e s [ i ] . l e n g t h 2 prerequisites[i].length 2 prerequisites[i].length2 0 ≤ a i , b i n u m C o u r s e s 0 \le a_i, b_i \lt numCourses 0≤ai,binumCourses p r e r e q u i s i t e s [ i ] prerequisites[i] prerequisites[i] 中的所有课程对 互不相同
解题过程
判断是否是有向无环图的模板题暴力的角度上看深搜和广搜都能做用图的入度来进行判断。 看了 灵神的题解 学到了三色标记法进一步了解到这种方法能够解决拓扑排序的问题决定目前的阶段先学到这种程度。 用三种状态来描述当前处理过程中节点的情况
如果当前节点尚未被访问用 0 0 0 来标记。如果当前节点正在访问中也就是当前正在处理与它相关的节点用 1 1 1来标记。如果当前节点已经访问完毕用 2 2 2 来标记。
如果图中无环那么不应该出现在处理相关节点的过程中遇到状态为正在访问中的节点的情况。
具体实现
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {ListInteger[] graph new ArrayList[numCourses];Arrays.setAll(graph, i - new ArrayList());// 根据先后要求建图所给二维数组中的第二个下标表示前置for(int[] item : prerequisites) {graph[item[1]].add(item[0]);}int[] colors new int[numCourses];for(int i 0; i numCourses; i) {if(colors[i] 0 dfs(i, graph, colors)) {return false;}}return true;}// 遍历方法返回的就是图中是否有环private boolean dfs(int cur, ListInteger[] graph, int[] colors) {// 将当前节点标记为访问中colors[cur] 1;// 依次访问这个从这个节点出发能够到达的所有节点for(int next : graph[cur]) {// 判断是否遇到访问中的节点并递归当前节点// 注意 Java 中逻辑与比逻辑或优先级要高这里如果没有发生或运算短路要先计算与if(colors[next] 1 || colors[next] 0 dfs(next, graph, colors)) {return true;}}// 将当前节点标记为已访问过colors[cur] 2;return false;}
}
