Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間6月前 (2025/05/26 20:07)推噓2(2推 0噓 1→)

好久沒發每日週賽也沒有發不過我每週都有比就懶得發而已我最近沒加啥分卡1900 我哭了題目: 有一張圖如果有環就回傳-1 不然就回傳圖上面所有路徑中最強的顏色最強的顏色 = 某條路徑出現最多次的顏色思路: 用bfs+indeg 好像叫啥khan的演算法反正就是可以依照順序遍歷有向圖同時用陣列dp記錄這樣可以順便檢測環這個最強的顏色用講的有點難說假設兩個路徑 1 : aaaabaaaaabbbbbb 2 : bbbb 雖然全部的話是b比較多 (11 但是a在路徑1出現9次這才是最多次 9才是答案用這個想的話就會發現每條路徑彼此根本就沒差但是如果要找路徑最常出現的顏色那就要記26種顏色這樣又會有一個問題假設路徑1跟2都到節點a 路徑1有三個a 路徑b有三個b 那這樣我不知道選哪個比較好所以我是假設每個顏色都是當前最多的每次bfs都會只看那個顏色這樣某個路徑出現最多次的話就更新答案那個顏色一定是真的最多次不然他就不會是最多次會被其他顏色替代對ㄚ ```cpp class Solution { public: int largestPathValue(string colors, vector<vector<int>>& edges) { int n = colors.size(); int m = edges.size(); int res = 0; queue<int> q; unordered_map<int,vector<int>> path; vector<int> indeg_(n); for(vector<int> k : edges) { path[k[0]].push_back(k[1]); indeg_[k[1]] ++; } for(int i = 0 ; i < n ; i ++) { if(indeg_[i] == 0) { q.push(i); } } for(int i = 0 ; i < 26 ; i ++) { vector<int> paper(n,0); vector<int> indeg = indeg_; queue<int> qq = q; while(!qq.empty()) { int now = qq.front(); qq.pop(); if(colors[now]-'a' == i)paper[now] ++; for(int nxt : path[now]) { indeg[nxt] --; paper[nxt] = max(paper[nxt],paper[now]); if(indeg[nxt] == 0) { qq.push(nxt); } } } for(int j = 0 ; j < n ; j ++) { if(indeg[j] > 0)return -1; res = max(res,paper[j]); } } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.4.112 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748261260.A.084.html ※ 編輯: oin1104 (101.10.4.112 臺灣), 05/26/2025 20:08:46

推

pyrogenlisa

05/26 20:12, 6月前 , 1^F

05/26 20:12, 1^F

推

mrsonic

05/26 20:23, 6月前 , 2^F

05/26 20:23, 2^F

→

ttucse

05/26 21:36, 6月前 , 3^F

05/26 21:36, 3^F