Re: [閒聊] 每日LeetCode

作者: JIWP (JIWP)   2024-02-24 18:48:15
你版今天線蟲帥朝都去FF惹
剩我還在解每日leetcode,今天還是hard,我要吐了
2092. Find All People With Secret
有0~n-1個人,並且0有一個秘密,他告訴了firstPerson
有一個array meetings[x,y,time]
如果x、y其中一個人知道了秘密他就會告訴對方
而且一個人在同時間可以有多個meetings,假設他在time=i的時候知道了秘密
那麼在time=i跟他meeting的人都會知道秘密
請問最後會有多少人知道秘密
思路 :
直覺這是一題graph搭配union-find
建立find function來找該節點的group
將meeting按照時間排序
接著建立1個groups array,並且設值group[i]=i
將index 0、firstPerson設成0
去依照meeting時間遍歷meetings矩陣
每一次分別找meetings[i][0]、meetings[i][1]屬於哪個group
並且把較大的那個group的值更改成較小的group
要進到下個meeting時間的時候重置group矩陣
如果find(group,i)=0 那就將group[i]=0
不然group[i]=i
這個時間內有meetings的人才要重置,所以有一個array去紀錄該時間有誰meeting過
如果不紀錄,而是0~n全部重置會超出時間限制
最後去找group[i]=0的就是答案
golang code
func find(array *[]int, index int) int {
for (*array)[index] != index {
index = (*array)[index]
}
return index
}
func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
slices.SortFunc[[][]int, []int](meetings, func(i, j []int) int {
return i[2] - j[2]
})
group := make([]int, n)
for i := 0; i < n; i++ {
group[i] = i
}
group[firstPerson] = 0
i := 0
l := len(meetings)
temp := []int{}
for i < l {
time := meetings[i][2]
temp = temp[:0]
for i < l && meetings[i][2] == time {
g1 := find(&group, meetings[i][0])
g2 := find(&group, meetings[i][1])
group[max(g1, g2)] = min(g1, g2)
temp = append(temp, meetings[i][0], meetings[i][1])
i++
}
for _, val := range temp {
if find(&group, val) != 0 {
group[val] = val
} else {
group[val] = 0
}
}
}
ans := []int{}
for i:=0;i<n;i++{
if group[i]==0{
ans = append(ans, i)
}
}
return ans
}
作者: DJYOSHITAKA (Evans)   2024-02-24 18:54:00
大師...
作者: sustainer123 (caster)   2024-02-24 18:55:00
大師
作者: oin1104 (是oin的說)   2024-02-24 18:56:00
大師 教我
作者: wu10200512 (廷廷)   2024-02-24 18:57:00
大師
作者: NCKUEECS (小惠我婆)   2024-02-24 18:58:00
大師
作者: Che31128 (justjoke)   2024-02-24 19:01:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com