千问 LeetCode 2360.图中的最长环 JavaScript实现
好的,这是 LeetCode 2360. 图中的最长环 的 JavaScript 实现,同样采用时间戳法,高效且简洁。
/**
* @param {number[]} edges
* @return {number}
*/
var longestCycle = function(edges) {
const n = edges.length;
const visitTime = new Array(n).fill(0); // 记录每个节点第一次被访问的时间戳
let ans = -1;
let time = 0; // 全局时间戳
for (let i = 0; i < n; i++) {
if (visitTime[i] !== 0) continue; // 已访问过,跳过
const startTime = time; // 记录本轮开始的时间
let cur = i;
while (cur !== -1 && visitTime[cur] === 0) {
visitTime[cur] = ++time; // 记录访问时间
cur = edges[cur];
}
// 如果停在了本轮访问过的节点上,说明发现了环
if (cur !== -1 && visitTime[cur] > startTime) {
ans = Math.max(ans, time - visitTime[cur] + 1);
}
}
return ans;
};
代码要点说明:
1. 时间戳数组:visitTime 初始化为 0,表示未访问。
2. 每轮遍历:从每个未访问的节点出发,沿着 edges 走,边走边记录时间戳。
3. 发现环的条件:当遇到一个节点 cur,它的 visitTime[cur] 不为 0,且大于本轮开始时间 startTime,说明这个节点是在本轮遍历中被访问过的,即构成了环。
4. 环长计算:time - visitTime[cur] + 1,其中 time 是当前时间戳(已自增到下一个未访问节点),visitTime[cur] 是环上节点的起始时间戳。
示例验证:
// 示例 1
edges = [3,3,4,2,3]
// 输出: 3
// 解释: 最长环 2 -> 4 -> 3 -> 2,长度为 3
// 示例 2
edges = [2,-1,3,1]
// 输出: -1
// 解释: 无环
复杂度分析:
- 时间复杂度:O(n),每个节点恰好被访问一次。
- 空间复杂度:O(n),用于 visitTime 数组。
另一种写法(使用 Map 记录本轮路径):
var longestCycle = function(edges) {
const n = edges.length;
const visited = new Array(n).fill(false);
let ans = -1;
for (let i = 0; i < n; i++) {
if (visited[i]) continue;
const timeMap = new Map(); // 记录本轮路径中节点的时间
let cur = i;
let time = 0;
while (cur !== -1 && !visited[cur]) {
timeMap.set(cur, time++);
visited[cur] = true;
cur = edges[cur];
}
if (cur !== -1 && timeMap.has(cur)) {
ans = Math.max(ans, time - timeMap.get(cur));
}
}
return ans;
};
不过第一种时间戳法更省空间(只用数组,不用 Map),推荐使用。
更多推荐



所有评论(0)