2024-02-07：用go语言，一个公司准备组织一场会议，邀请名单上有 n 位员工， 公司准备了一张 圆形 的桌子，可以坐下

2024-02-07：用go语言，一个公司准备组织一场会议，邀请名单上有 n 位员工，

公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工，

员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，

每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议，

每位员工喜欢的员工 不会 是他自己。

给你一个下标从 0 开始的整数数组 favorite，

其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目。

输入：favorite = [2,2,1,2]。

输出：3。

答案2024-02-07：

来自左程云。

灵捷3.5

大体步骤如下：

1.创建一个名为maximumInvitations的函数，接受一个整数数组favorite作为参数。函数返回值为最多能参加会议的员工数目。

2.在maximumInvitations函数中，首先调用beLoved函数生成一个被喜欢表，表示每个员工喜欢的员工。

3.调用calculateDegree函数计算每个员工的入度，即喜欢该员工的员工数目。

4.初始化一个队列queue，利用队列进行拓扑排序。

5.将所有入度为 0 的员工加入队列queue。

6.使用zeroVisited数组记录已经访问过的员工。

7.当队列不为空时，从队列中取出一个员工，并标记为已访问。

8.遍历该员工喜欢的员工列表，将其入度减一，若入度减为 0，则将该员工添加到队列中。

9.使用cycleVisited数组记录已经访问过的员工，同时统计环上的员工数目。

10.如果某个员工的喜欢的员工也喜欢自己，则说明存在一个长度为 2 的环，更新arrangeTwoCycle变量。

11.否则，遍历环上的员工，找到最长的环，更新arrangeMoreCycle变量。

12.比较arrangeTwoCycle和arrangeMoreCycle的值，取较大值作为最终结果。

13.返回最终结果。

总的时间复杂度和额外空间复杂度分别如下：

• 时间复杂度：O(n^2)，其中 n 是员工数目。遍历每个员工需要 O(n) 的时间，同时查找和更新相关信息的操作也可能需要 O(n) 的时间。

• 空间复杂度：O(n)，需要额外的空间来存储喜欢关系、度数、访问状态等信息。

go完整代码如下：

package main

import "fmt"

func maximumInvitations(favorite []int) int {

loved := beLoved(favorite)

degree := calculateDegree(loved)

n := len(favorite)

queue := make([]int, n)

l := 0

r := 0

for i := 0; i < n; i++ {

if degree[i] == 0 {

queue[r] = i

r++

}

}

zeroVisited := make([]bool, n)

for l < r {

cur := queue[l]

l++

zeroVisited[cur] = true

if degree[favorite[cur]]--; degree[favorite[cur]] == 0 {

queue[r] = favorite[cur]

r++

}

}

cycleVisited := make([]bool, n)

arrangeTwoCycle := 0

arrangeMoreCycle := 0

for i := 0; i < n; i++ {

if !zeroVisited[i] && !cycleVisited[i] {

cycleVisited[i] = true

if favorite[favorite[i]] == i {

cycleVisited[favorite[i]] = true

arrangeTwoCycle += maxFollow(i, zeroVisited, loved) + maxFollow(favorite[i], zeroVisited, loved)

} else {

cur := favorite[i]

curAns := 1

for cur != i {

cycleVisited[cur] = true

curAns++

cur = favorite[cur]

}

if curAns > arrangeMoreCycle {

arrangeMoreCycle = curAns

}

}

}

}

if arrangeTwoCycle > arrangeMoreCycle {

return arrangeTwoCycle

}

return arrangeMoreCycle

}

// 生成被喜欢表

func beLoved(favorite []int) [][]int {

n := len(favorite)

size := make([]int, n)

for _, love := range favorite {

size[love]++

}

loved := make([][]int, n)

for i := 0; i < n; i++ {

loved[i] = make([]int, size[i])

}

for i, f := range favorite {

size[f]--

loved[f][size[f]] = i

}

return loved

}

// 求每个点的入度

func calculateDegree(loved [][]int) []int {

n := len(loved)

degree := make([]int, n)

for i := 0; i < n; i++ {

degree[i] = len(loved[i])

}

return degree

}

// cur不在环上的追随者链条最大长度

func maxFollow(cur int, zeroed []bool, from [][]int) int {

if len(from[cur]) == 0 {

return 1

}

ans := 0

for _, pre := range from[cur] {

if zeroed[pre] {

follow := maxFollow(pre, zeroed, from)

if follow > ans {

ans = follow

}

}

}

return ans + 1

}

func main() {

favorite := []int{1, 2, 0}

result := maximumInvitations(favorite)

fmt.Println(result)

}

在这里插入图片描述