这道题是最小生成树板子题
可以用并查集实现,贪心排序边权
讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树
代码有点套娃(
class Solution { private: int fa[1007]; int cnt = 0; typedef pair<int, pair<int, int> > pir; void init() { for (int i = 0; i < 1007; i++) fa[i] = i; } int _find(int u) { if (fa[u] == u) return u; else return fa[u] = _find(fa[u]); } public: int minCostConnectPoints(vector<vector<int>> &points) { init(); vector<pir> vt; int n = points.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int wei = abs(points[i][0] - points[j][0]); wei += abs(points[i][1] - points[j][1]); vt.push_back({wei, {i, j}}); } } sort(vt.begin(), vt.end(), [](pir p1, pir p2) { return p1.first < p2.first; }); long long out = 0; int lim = vt.size(); for (int i = 0; i < lim; i++) { int u = vt[i].second.first; int v = vt[i].second.second; int fau = _find(fa[u]); int fav = _find(fa[v]); if (fau == fav) continue; else { fa[fau] = fav; out += vt[i].first; } } return out; } };
文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成8242 人正在系统学习中