参加会议的最多员工数
难度:
标签:
题目描述
一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
示例 1：
输入：favorite = [2,2,1,2] 输出：3 解释： 上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。 没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。 注意，公司也可以邀请员工 1，2 和 3 参加会议。 所以最多参加会议的员工数目为 3 。
示例 2：
输入：favorite = [1,2,0] 输出：3 解释： 每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。 座位安排同图 1 所示： - 员工 0 坐在员工 2 和 1 之间。 - 员工 1 坐在员工 0 和 2 之间。 - 员工 2 坐在员工 1 和 0 之间。 参与会议的最多员工数目为 3 。
示例 3：
输入：favorite = [3,0,1,4,1] 输出：4 解释： 上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。 员工 2 无法参加，因为他喜欢的员工 1 旁边的座位已经被占领了。 所以公司只能不邀请员工 2 。 参加会议的最多员工数目为 4 。
提示：
n == favorite.length2 <= n <= 1050 <= favorite[i] <= n - 1favorite[i] != i
代码结果
运行时间: 163 ms, 内存: 28.8 MB
// Solution using Java Stream
/*
* 思路：
* 使用流的方式遍历和处理数组。我们可以使用intStream来进行遍历，
* 对于每个员工，我们将他们的喜欢关系进行映射和统计。
*/
import java.util.*;
import java.util.stream.*;
public class MaxEmployeesMeetingStream {
public int maxEmployees(int[] favorite) {
int n = favorite.length;
int[] visited = new int[n];
int[] longestCycle = {0};
IntStream.range(0, n).forEach(i -> {
if (visited[i] == 0) {
Set<Integer> currentCycle = new HashSet<>();
int curr = i;
while (!currentCycle.contains(curr) && visited[curr] == 0) {
currentCycle.add(curr);
visited[curr] = 1;
curr = favorite[curr];
}
if (currentCycle.contains(curr)) {
int cycleLength = 1;
int start = favorite[curr];
while (start != curr) {
cycleLength++;
start = favorite[start];
}
longestCycle[0] = Math.max(longestCycle[0], cycleLength);
}
}
});
int pairsMax = IntStream.range(0, n)
.filter(i -> favorite[favorite[i]] == i && visited[i] == 1)
.distinct()
.map(i -> 2)
.sum();
return Math.max(longestCycle[0], pairsMax);
}
}
解释
方法:
本题解利用了图论中基环树（cactus）的概念，将问题转化为在有向图中找到最大的基环树的大小。首先，通过计算每个员工被喜欢的次数（即入度），可以识别并删除所有的树枝，这是通过拓扑排序实现的。在拓扑排序过程中，我们也计算了从每个树叶到其树根的最长路径长度。其次，对于残留在图中的环，我们需要特别处理长度为2的环，因为这种环可以利用其外部的链条来增加参与会议的人数。最后，比较由长度为2的环构成的链和最大环的大小，返回最大值，即为最多可能参加会议的员工数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
如何确保每个节点只被访问一次，在拓扑排序的实现中？
▷🦆
为什么要特别处理长度为2的环，它们在这个问题中有什么特殊性质？
▷🦆
在处理长度为2的环时，`max_depth[i] + max_depth[favorite[i]]` 这个公式是如何得出的？
▷🦆
算法中提到的基环树的概念在哪里体现？具体是怎样利用这一概念解决问题的？
▷