如何做网站定位,私人定制平台网站,营销网站与企业网站的区别,重庆城乡建设局网站【力扣】2127. #xff08;分类讨论 拓扑排序#xff09;参加会议的最多员工数 文章目录 【力扣】2127. #xff08;分类讨论 拓扑排序#xff09;参加会议的最多员工数1. 题目介绍2. 思路#xff08;**分类讨论 拓扑排序**#xff09;3. 解题代码4. Danger参考 1. 题…【力扣】2127. 分类讨论 拓扑排序参加会议的最多员工数 文章目录 【力扣】2127. 分类讨论 拓扑排序参加会议的最多员工数1. 题目介绍2. 思路**分类讨论 拓扑排序**3. 解题代码4. Danger参考 1. 题目介绍
一个公司准备组织一场会议邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子可以坐下 任意数目 的员工。 要求员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工每位员工当且仅当他被安排在喜欢员工的旁边他才会参加会议。每位员工喜欢的员工 不会 是他自己。 给你一个下标从 0 开始的整数数组 favorite 其中 favorite[i] 表示第 i 位员工喜欢的员工。 请你返回参加会议的 最多员工数目 。
示例
1 2 3
提示
2. 思路分类讨论 拓扑排序
首先需要简单了解一下 基环内向树。在了解了树的基础上来解释基环树——树加一条边使之成环也就是说在严格意义上来说基环树并不是树就像老婆饼没有老婆一样基环树是个图。首先它是一个有向图它构成类似基环树的结构。
最重要的特点就是每个点都有且只有一个出度并且环外的节点方向指向环内。
针对这道题我们可以把每个员工看成图上的一个节点如果员工 x 喜欢员工 y就在从 x 对应的节点到 y 对应的节点连一条边那么形成的图则是会由若干颗「基环内向树」组成就是形如下图所示的结构 原因如下
我们从任意一个节点 x 开始在图上进行「游走」由于每个员工只有一位喜欢的员工因此每个节点在图上只会有一条出边即「游走」的过程是唯一的。由于图上有 n 个节点因此在 n1 步以内一定会走到一个重复的节点那么在第一次经过该节点之后到第二次经过该节点之前的所有节点以及该节点本身就组成了一个环如上图的蓝色节点所示。对于不在环上的节点我们已经说明了从它们开始「游走」也一定会进入到环中。在到达环上的节点之前它们不会重复经过节点否则就有两个环了我们可以证明一个连通分量中是不可能有两个环的因为每个节点只有一条出边因此如果有两个环并且它们连通那么必然某个环上有一个点有两条出边一条出边指向同一个环上的节点另一条出边可以使得它到达另一个环这就产生了矛盾那么它们就形成了类似树的结构如上图的绿色节点所示。需要注意的是一个单独的环也是「基环内向树」它是一种特殊情况即没有绿色的节点。
思路与算法既然我们知道了图由若干颗「基环内向树」组成那么我们只需要计算每一颗「基环内向树」的哪一部分可以被安排参加会议就可以来接这道题目。
1首先讨论特殊的情况即一个单独的环或若干个环并且所有环的大小都 ≥3。可以发现我们按照环上的顺序给对应的员工安排座位是满足要求的因为对于每一个环上的员工它喜欢的员工就在它的旁边。并且我们必须安排环上的所有员工因为如果有缺失那么喜欢那位缺失了的员工的员工就无法满足要求了。 但如果我们已经安排了某一个环上的所有员工剩余的环就没有办法安排了。这是因为已经安排的那个环是没有办法被「断开」的断开的本质就是相邻位置员工的缺失。因此我们可以得出一个重要的结论 如果我们想安排大小 ≥3 的环我们最多只能安排一个并且环需要是完整的。 2接下来是形成的图是 环大小 ≥3 的「基环内向树」如果我们安排了不在环上的节点那么从该节点开始我们需要不断安排当前节点喜欢的员工这实际上就是「游走」的过程。 而当我们游走到环上并到达环上最后一个未经过的节点时该节点的下一个节点即喜欢的员工已经被安排过所以最后一个未经过的节点就无法被安排因为下一个节点不是他的喜欢节点不满足要求。因此我们不能安排任何不在环上的节点只能安排在环上的节点就得出了另一个的结论 所有环大小 ≥3 的「基环内向树」与一个大小相同指环的部分的环是等价的。 3最后需要考虑大小 2 的环或者「基环内向树」了。 这里的特殊之处在于大小 2 的环可以安排多个因为环上的两个点是互相喜欢的因此只需要它们相邻即可而没有其它的要求。而对于环大小 2 的「基环内向树」如果我们安排了不在环上的节点那么游走完环上两个节点之后同样是满足要求的并且我们甚至可以继续延伸反向「游走」到另一个不在环上的节点为止。如下图所示包含 X 的节点就是可以安排参加会议的节点。 并且同样地对于每一棵环大小 2 的「基环内向树」我们都可以取出这样一条「双向游走」路径进行安排它们之间不会影响。
综上所述原问题的答案即为下面二者中的最大值
最大的环的大小所有环大小 2 的「基环内向树」上的最长的「双向游走」路径之和。
为了求解「基环内向树」上的最长的「双向游走」路径我们可以使用拓扑排序 动态规划的方法。记 f[i] 表示到节点 i 为止的最长「游走」路径经过的节点个数那么状态方程即为
即我们考虑节点 i 的上一个节点 j在图中必须有从 j 到 i 的一条有向边这样我们就可以从 j 转移到 i。如果不存在满足要求的 j例如「基环内向树」退化成一个大小 2 的环那么 f[i]1。状态转移可以和拓扑排序同时进行。在拓扑排序完成后剩余没有被弹出过队列的节点就是环上的节点。我们可以找出每一个环。如果环的大小 ≥3我们就用其来更新最大的环的大小如果环的大小 2设环上的两个节点为 x 和 y那么该「基环内向树」上最长的「双向游走」的路径长度就是 f[x]f[y]。
时间复杂度O(n)。图中有 n 个节点和 n 条边拓扑排序需要的时间为 O(n)后续找出所有环的时间也为 O(n)。 空间复杂度O(n)。我们需要若干个长度为 n 的数组。
3. 解题代码
class Solution:def maximumInvitations(self, favorite: List[int]) - int:n len(favorite)# 统计入度便于进行拓扑排序indeg [0] * nfor i in range(n):indeg[favorite[i]] 1used [False] * nf [1] * nq deque(i for i in range(n) if indeg[i] 0)while q:u q.popleft()used[u] Truev favorite[u]# 状态转移f[v] max(f[v], f[u] 1)indeg[v] - 1if indeg[v] 0:q.append(v)# ring 表示最大的环的大小# total 表示所有环大小为 2 的「基环内向树」上的最长的「双向游走」路径之和ring total 0for i in range(n):if not used[i]:j favorite[i]# favorite[favorite[i]] i 说明环的大小为 2if favorite[j] i:total f[i] f[j]used[i] used[j] True# 否则环的大小至少为 3我们需要找出环else:u icnt 0while True:cnt 1u favorite[u]used[u] Trueif u i:breakring max(ring, cnt)return max(ring, total)4. Danger
力扣LeetCode是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷力扣为全球程序员提供了专业的IT技术职业化提升平台有效帮助程序员实现快速进步和长期成长。此外力扣LeetCode致力于解决程序员技术评估、培训、职业匹配的痛点逐步引领互联网技术求职和招聘迈向专业化。
据了解到的情况Easy题和Medium 题在面试中比较常见通常会以手写代码之类的形式出现您需要对问题进行分析并给出解答并于面试官进行交流沟通有时还会被要求分析时间复杂度8与空间复杂度°面试官会通过您对题目的分析解答了解您对常用算法的熟悉程度和您的程序实现功底。而在一些对算法和程序实现功底要求较高的岗位Hard 题也是很受到面试官的青睐如果您在面试中成功Bug-Free出一道Hard题我们相信您一定会给面试官留下很深刻的印象并极大增加拿到Offer的概率据相关人士统计如果您在面试成功解出一道Hard题拿不到Offer的概率无限接近于0。所以,力扣中Easy和Medium相当于面试中的常规题而Hard 则相当于面试中较难的题解出—道Hard题Offer可以说是囊中之物。
参考
【1】https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/?envTypedaily-questionenvId2023-11-01 【2】https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/solutions/1190222/can-jia-hui-yi-de-zui-duo-yuan-gong-shu-u8e8u/
