Re: [閒聊] 每日leetcode
要過年了
我怎麼還在寫每日，一定有哪裡搞錯了
2127. Maximum Employees to Be Invited to a Meeting
思路：
就是去找最長cycle的長度
又可以依照cycle長度分成兩種情況
1.長度 > 2
就單純紀錄cycle的長度就好
2.長度 = 2
這個比較麻煩一點
假設是i、j形成cycle
那你要記錄到i最長的長度 + 到j最長的長度才會是可以圍成圓桌的人數
接著每一個cycle長度 = 2的圓桌可以合併相加起來
就照上述兩種情況去處理就好
golang code :
type node_info struct {
depth int //該node(包含)以前有幾個node
length int //該node(包含)以後有幾個node
end_node int // -1表示還形成cycle -2表示已經形成cycle，且cycle長度>2 其他表
示cycle長度=2
}
func maximumInvitations(favorite []int) int {
n, ans := len(favorite), 0
var dfs func(node, depth int) int
nodes, visited := make([]node_info, n), make([]bool, n)
for i := 0; i < n; i++ {
nodes[i].end_node = -1
if favorite[favorite[i]] == i {
nodes[i].length = 1
nodes[favorite[i]].length = 1
visited[i], visited[favorite[i]] = true, true
nodes[i].end_node = i
nodes[favorite[i]].end_node = favorite[i]
}
}
dfs = func(node, depth int) int {
visited[node] = true
nodes[node].depth = depth
next_node := favorite[node]
if visited[next_node] {
if nodes[next_node].end_node == -2 {
nodes[node].end_node = -2
return -1
} else if nodes[next_node].end_node == -1 {
nodes[node].end_node = -2
nodes[node].length = 1
ans = max(ans, depth-nodes[next_node].depth+1)
return 1
} else {
end_node := nodes[next_node].end_node
if end_node == next_node {
if depth+1 > nodes[end_node].length {
nodes[end_node].length = depth + 1
}
nodes[node].length = 2
} else {
if nodes[end_node].length < depth+nodes[next_node].length {
nodes[end_node].length = depth + nodes[next_node].length
}
nodes[node].length = nodes[next_node].length + 1
}
nodes[node].end_node = end_node
return nodes[node].length
}
} else {
length := dfs(next_node, depth+1)
nodes[node].length = length + 1
nodes[node].end_node = nodes[next_node].end_node
return nodes[node].length
}
}
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i, 1)
}
}
tmp := 0
for i := 0; i < n; i++ {
nodes[i].end_node = -1
if favorite[favorite[i]] == i {
tmp += nodes[i].length
}
}
return max(tmp, ans)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.38.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737890650.A.C92.html
推
01/26 19:27,
10月前
, 1F
01/26 19:27, 1F
推
01/26 20:59,
10月前
, 2F
01/26 20:59, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1308 之 1552 篇)：