Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/10/07 14:02)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串956/1548 (看更多)

每日太水來寫個不一樣的題目; 1584. Min cost to connect all point 用最短的路把所有點都連在一起路徑長直接用x跟y的差距就好叫啥曼哈頓距離的思路: 因為只要全部連在一起所以誰連誰都可以用map記所有人的路徑然後隨便一個點開始每次都找最近的連這樣一定可以找到最短的路自己寫了一些幹東西筆記 unordered map的hash value 需要弄運算子== 作為比較時的方法 priority queue 需要弄運算子>或< 當作greater或less比較的方法 ```cpp struct point { int x ; int y ; int idx ; bool operator<(const point& other) const { if (x == other.x) return y < other.y; return x < other.x; } bool operator==(const point& other) const { return x == other.x && y == other.y && idx == other.idx; } }; struct point_hash { std::size_t operator() (const point &p) const { std::size_t h1 = std::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(p.y); return h1 ^ (h2 << 1); } }; class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { unordered_map<point,vector<point> , point_hash> save; int n = points.size(); for(int i = 0 ; i < n ; i ++) { point now; now.x = points[i][0]; now.y = points[i][1]; now.idx = i; for(int j = i+1 ; j < n ; j ++){ point next; next.x = points[j][0]; next.y = points[j][1]; next.idx = j ; save[now].push_back(next); save[next].push_back(now); } } point first; first.x = points[0][0]; first.y = points[0][1]; first.idx = 0; priority_queue<pair<int,point> , vector<pair<int,point>> , greater<pair< int,point>> > pq; pq.push({0,first}); vector<int> passed(n,0); int nowpass = 0; int all = 0; while(!pq.empty()) { int nowdist = pq.top().first; point now = pq.top().second; pq.pop(); if(passed[now.idx])continue; passed[now.idx] = 1; all += nowdist; nowpass ++; if(nowpass == n)return all; for(point next : save[now]){ int dist = abs(next.x-now.x) + abs(next.y - now.y); pq.push({dist,next}); } } return all; } }; ``` -- 邊版的小母雞 — fuckchicken https://i.imgur.com/wglAuYR.jpg