wordpress多站点,免费网站模板psd,博采网站建设,石家庄seo扣费题目描述 这是 LeetCode 上的 「2127. 参加会议的最多员工数」 #xff0c;难度为 「困难」。 Tag : 「拓扑排序」、「内向基环树」、「图」 一个公司准备组织一场会议#xff0c;邀请名单上有 n 位员工。 公司准备了一张圆形的桌子#xff0c;可以坐下任意数目的员工。 员工… 题目描述 这是 LeetCode 上的 「2127. 参加会议的最多员工数」 难度为 「困难」。 Tag : 「拓扑排序」、「内向基环树」、「图」 一个公司准备组织一场会议邀请名单上有 n 位员工。 公司准备了一张圆形的桌子可以坐下任意数目的员工。 员工编号为 到 。每位员工都有一位喜欢的员工每位员工当且仅当他被安排在喜欢员工的旁边他才会参加会议每位员工喜欢的员工不会是他自己。 给你一个下标从 开始的整数数组 favorite其中 表示第 位员工喜欢的员工。请你返回参加会议的最多员工数目。 示例 1 输入favorite [2,2,1,2]输出3解释上图展示了公司邀请员工 01 和 2 参加会议以及他们在圆桌上的座位。没办法邀请所有员工参与会议因为员工 2 没办法同时坐在 01 和 3 员工的旁边。注意公司也可以邀请员工 12 和 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解释上图展示了公司可以邀请员工 013 和 4 参加会议以及他们在圆桌上的座位。员工 2 无法参加因为他喜欢的员工 0 旁边的座位已经被占领了。所以公司只能不邀请员工 2 。参加会议的最多员工数目为 4 。 提示 内向基环树 拓扑排序 根据题意圆形桌上 左右两边只要有一位是 所喜欢即可。 我们可从 向 添加有向边从而得到一张包含多个「内向基环树」的图。 内向基环树是指其满足基环树定义且内向 bushi。 基环树是指其具有 个点 条边的联通块而「内向」是指树中任意节点有且只有一条出边对应的「外向」是指树中任意节点有且只有一条入边。 例如左图内向右图外向 根据题意「圆桌最多放置一个长度大于 的环内向环只有一条出边即只有一个喜欢的人安插其他非环成员会破坏留下参加会议的必要条件但可放置多个长度为 的环且多个环可延伸出最长链利用左右两侧只需有一个喜欢的人即满足。」 在「取长度大于 的最大环」及「多个长度为 的环及其最长链之和」两者中取最大长度即是答案。 Java 代码 class Solution { public int maximumInvitations(int[] favorite) { int n favorite.length; // in 统计每个节点的入度情况, max 统计节最长链 int[] in new int[n], max new int[n]; for (int x : favorite) in[x]; DequeInteger d new ArrayDeque(); for (int i 0; i n; i) { if (in[i] 0) d.addLast(i); } // 拓扑排序: 求基环外的最长链 while (!d.isEmpty()) { int cur d.pollFirst(), ne favorite[cur]; max[ne] Math.max(max[ne], max[cur] 1); if (--in[ne] 0) d.addLast(ne); } // 圆桌最多放置一个大于 2 的环ans1 统计最大值 // 圆桌可放置多个等于 2 的环ans2 累加该长度 int ans1 0, ans2 0; for (int i 0; i n; i) { if (in[i] 0) continue; int j favorite[i], cur 1; while (j ! i) { // 一个环只需被处理一次, 这里将环中其他节点入度置 0, 下次遍历到这些点就会被跳过 in[j] 0; j favorite[j]; cur; } if (cur 2) ans2 2 max[i] max[favorite[i]]; else ans1 Math.max(ans1, cur); } return Math.max(ans1, ans2); }} Python 代码 class Solution: def maximumInvitations(self, favorite: List[int]) - int: n len(favorite) # in_degree 统计每个节点的入度情况, max_length 统计节最长链 in_degree, max_length [0] * n, [0] * n for x in favorite: in_degree[x] 1 d deque() for i in range(n): if in_degree[i] 0: d.append(i) # 拓扑排序: 求基环外的最长链 while d: cur d.popleft() ne favorite[cur] max_length[ne] max(max_length[ne], max_length[cur] 1) in_degree[ne] - 1 if in_degree[ne] 0: d.append(ne) # 圆桌最多放置一个大于 2 的环ans1 统计最大值 # 圆桌可放置多个等于 2 的环ans2 累加该长度 ans1, ans2 0, 0 for i in range(n): if in_degree[i] 0: continue j, cur favorite[i], 1 while j ! i: # 一个环只需被处理一次, 这里将环中其他节点入度置 0, 下次遍历到这些点就会被跳过 in_degree[j] 0 j favorite[j] cur 1 if cur 2: ans2 2 max_length[i] max_length[favorite[i]] else: ans1 max(ans1, cur) return max(ans1, ans2) C 代码 class Solution {public: int maximumInvitations(vectorint favorite) { int n favorite.size(); // in 统计每个节点的入度情况, max_length 统计节最长链 vectorint in(n, 0); vectorint max_length(n, 0); for (int x : favorite) in[x]; dequeint d; for (int i 0; i n; i) { if (in[i] 0) d.push_back(i); } // 拓扑排序: 求基环外的最长链 while (!d.empty()) { int cur d.front(); d.pop_front(); int ne favorite[cur]; max_length[ne] max(max_length[ne], max_length[cur] 1); if (--in[ne] 0) d.push_back(ne); } // 圆桌最多放置一个大于 2 的环ans1 统计最大值 // 圆桌可放置多个等于 2 的环ans2 累加该长度 int ans1 0, ans2 0; for (int i 0; i n; i) { if (in[i] 0) continue; int j favorite[i], cur 1; while (j ! i) { // 一个环只需被处理一次, 这里将环中其他节点入度置 0, 下次遍历到这些点就会被跳过 in[j] 0; j favorite[j]; cur; } if (cur 2) ans2 2 max_length[i] max_length[favorite[i]]; else ans1 max(ans1, cur); } return max(ans1, ans2); }}; TypeScript 代码 function maximumInvitations(favorite: number[]): number { const n favorite.length; // in_degree 统计每个节点的入度情况, max_length 统计节最长链 const in_degree Array(n).fill(0), max_length Array(n).fill(0); for (const x of favorite) in_degree[x]; const d []; for (let i 0; i n; i) { if (in_degree[i] 0) d.push(i); } // 拓扑排序: 求基环外的最长链 while (d.length 0) { const cur d.shift() as number; const ne favorite[cur]; max_length[ne] Math.max(max_length[ne], max_length[cur] 1); if (--in_degree[ne] 0) d.push(ne); } // 圆桌最多放置一个大于 2 的环ans1 统计最大值 // 圆桌可放置多个等于 2 的环ans2 累加该长度 let ans1 0, ans2 0; for (let i 0; i n; i) { if (in_degree[i] 0) continue; let j favorite[i], cur 1; while (j ! i) { // 一个环只需被处理一次, 这里将环中其他节点入度置 0, 下次遍历到这些点就会被跳过 in_degree[j] 0; j favorite[j]; cur; } if (cur 2) ans2 2 max_length[i] max_length[favorite[i]]; else ans1 Math.max(ans1, cur); } return Math.max(ans1, ans2);}; 时间复杂度统计入度的复杂度为 拓扑排序求最长链复杂度为 计算答案过程中每个点最多被访问两次环内节点复杂度为 。整体复杂度为 空间复杂度 最后 这是我们「刷穿 LeetCode」系列文章的第 No.2217 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
