Re: [閒聊] 每日leetcode
寫一下每日來騙個p幣
1857. Largest Color Value in a Directed Graph
題目
在一個有向圖中有n個點m條邊
每個點都有一個顏色
定義color value為一個path中最常出現的color的出現次數
請問在這個圖中的所有path中最大的color value
如果圖中有cycle則回傳-1
思路:
首先找indegree為0的點，把這些點當成起點去做dfs
接著每個點都用一個array紀錄由該點出發的所有路徑每個顏色出現的最大次數
如果我們發現這個點跑過了，就可以不用跑直接去看那個array紀錄的顏色次數
從起點跑完所有path就可以得到答案了
然後在過程中注意有沒有cycle就好
golang code :
func largestPathValue(colors string, edges [][]int) int {
n, ans,cnt := len(colors), 0,0
paths, indegree, visited, rec := make([][]int, n), make([]int, n), make([]
bool, n), make([][26]int, n)
colorsIdx := make([]byte, n)
var dfs func(node int, chk []bool) bool
dfs = func(node int, chk []bool) bool {
if chk[node] {
return true
}
chk[node] = true
if len(paths[node]) == 0 {
rec[node][int(colorsIdx[node]-'a')]++
chk[node] = false
return false
}
for _, val := range paths[node] {
if !visited[val] {
if dfs(val, chk) {
return true
}
cnt++
visited[val] = true
}
for i := 0; i < 26; i++ {
rec[node][i] = max(rec[node][i], rec[val][i])
}
}
rec[node][int(colorsIdx[node]-'a')]++
chk[node] = false
return false
}
for i := 0; i < n; i++ {
colorsIdx[i] = byte(colors[i])
}
for _, path := range edges {
from, to := path[0], path[1]
indegree[to]++
paths[from] = append(paths[from], to)
}
starts := []int{}
for key, val := range indegree {
if val == 0 {
starts = append(starts, key)
}
}
for _, val := range starts {
chk := make([]bool, n)
if !visited[val] {
hasCycle := dfs(val, chk)
if hasCycle {
return -1
}
cnt++
visited[val] = true
}
for i := 0; i < 26; i++ {
ans = max(ans, rec[val][i])
}
}
if cnt != n{return -1}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748358602.A.8EE.html
推
05/27 23:30,
6月前
, 1F
05/27 23:30, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1438 之 1548 篇)：