佛山建设企业网站,微网站功能,熊猫办公ppt模板下载,wordpress中科大字体说在前面 #x1f388;不知道大家对于算法的学习是一个怎样的心态呢#xff1f;为了面试还是因为兴趣#xff1f;不管是处于什么原因#xff0c;算法学习需要持续保持#xff0c;今天让我们一起来看看这一道题目————图中的最长环#xff0c;图论题目中比较常见的环路…说在前面 不知道大家对于算法的学习是一个怎样的心态呢为了面试还是因为兴趣不管是处于什么原因算法学习需要持续保持今天让我们一起来看看这一道题目————图中的最长环图论题目中比较常见的环路问题。 题目描述
给你一个 n 个节点的 有向图 节点编号为 0 到 n - 1 其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边那么 edges[i] -1 。
请你返回图中的 最长 环如果没有任何环请返回 -1 。
一个环指的是起点和终点是 同一个 节点的路径。
示例 1 输入edges [3,3,4,2,3]
输出去3
解释图中的最长环是2 - 4 - 3 - 2 。
这个环的长度为 3 所以返回 3 。示例 2 输入edges [2,-1,3,1]
输出-1
解释图中没有任何环。提示
n edges.length
2 n 10^5
-1 edges[i] n
edges[i] ! i思路分析
题目的要求很清晰就是要我们找出单向连通图中的最长环那么在一个图中我们要怎样来判断有没有存在环呢因为这道题目中的图是单向图所以我们可以很简单找出图中的环如下图 我们从节点1出发遍历过的节点都做上标记然后不断的往图的下一个节点遍历直到遇到已经做过标记的节点则说明其前面也遍历过也即是已经形成了环。这样说的话我们是不是可以把所有节点都当成起点走一遍找出所有环中的最长环就可以让我们动手写代码试一下按照这个思路我们可以写出这样一段代码
/*** param {number[]} edges* return {number}*/var longestCycle function(edges) {let res -1;const dfs (node,steps,step 0){if(edges[node] -1) return -1;if(steps[node] step){res Math.max(step - steps[node],res);return step;}steps[node] step;dfs(edges[node],steps,step 1);}for(let i 0; i edges.length; i){dfs(i,new Array(edges.length).fill(Infinity));}return res 0 ? res : -1;
};测试一下好像没问题然后自信提交代码 回头看一下数据规模2 n 10^5,这样做确实太暴力了那就来看看可以怎么优化 上图中橙色路径为从节点1出发的遍历路线蓝色路径为从节点2出发的遍历路线从图中我们可以很明显的看成蓝色路线是橙色路线中的一部分因为节点2在节点1的遍历路径中所以节点2往后的遍历路线一定是包含在节点1的遍历路线中所以我们可以记录一下每个节点的遍历情况如果是已经遍历过的节点的话我们不应该重复遍历所以代码可以这样进行优化
使用一个数组来记录遍历过程中每一个节点的遍历情况(visited)使用一个map来存放在当前路径中已经遍历过的节点所需步数(steps)遇到map中存在的节点时更新最长环长度
AC代码
/*** param {number[]} edges* return {number}*/var longestCycle function(edges) {let res -1;const dfs (node,steps {},step 0){if(visited[node] || steps[node] step || edges[node] -1){if(steps[node] step) res Math.max(step - steps[node],res);return;}steps[node] step; visited[node] true;dfs(edges[node],steps,step 1);}const visited new Array(edges.length).fill(false);for(let i 0; i edges.length; i) dfs(i);return res;
};公众号
关注公众号『前端也能这么有趣』获取更多有趣内容。
说在后面 这里是 JYeontu现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
