Re: [閒聊] 每日LeetCode

207. Course Schedule 這題就是標準的拓樸排序 但就這樣乖乖照著寫有點無聊 所以我們來利用 C++ 的 shared_ptr 因為 shared_ptr 只要沒有人指向他就會自己消滅 所以我們只要維護 adj, 其中 adj[a] = {Pointers[b], Pointers[c]} 代表要修 b c 之前必須修過 a, 也就是存在邊 [b, a], [c, a] 這樣沒有先修課 a 的就不會有人指向他 就會去呼叫 destructor 此時我們只要在 destructor 裡把 adj[a] 清空 如果有人因此變得沒人指向他的話就會接著呼叫他的 destructor 可以說跟這題完美契合 事情都讓 shared_ptr 做完了 最後只要算一下呼叫了幾次 destructor 就好 :) ---------------------------------------------- struct T { bool& flag; int& cnt; vector<shared_ptr<T>>& row; T(bool& flag, int& cnt, vector<shared_ptr<T>>& row) : flag(flag), cnt(cnt), row(row) {} ~T() { if (flag) { row.clear(); cnt -= 1; } } }; class Solution { public: bool canFinish(int n, vector<vector<int>>& prerequisites) { bool flag = true; int cnt = n; vector<shared_ptr<T>> V(n); vector<vector<shared_ptr<T>>> adj(n); for (int i = 0; i < n; i++) V[i] = make_shared<T>(flag, cnt, adj[i]); for (auto& req: prerequisites) { int a = req[0], b = req[1]; adj[b].push_back(V[a]); } V.clear(); flag = false; return cnt == 0; } }; ---------------------------------------------- -- https://i.imgur.com/tLHo8xr.png --
※ 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689270725.A.3DD.html

推 dannyko: 大師 07/14 01:59