Szczegółowe omówienie zadania Min Cost to Connect All Points:
Link do powyższego omówienia zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=1117
Omówienie kodu który zadania Min Cost to Connect All Points: https://youtu.be/jOqGMOGJQ1s?t=4744
Link do treści zadania Min Cost to Connect All Points i możliwości umieszczania rozwiązań: https://leetcode.com/problems/min-cost-to-connect-all-points/
–
Zadanie pokazuje algorytm Find And Union: https://youtu.be/jOqGMOGJQ1s?t=2036
–
Zadanie z LeetCode – platformy która zawiera zadania z interview / rozmów kwalifikacyjnych do Google, Facebook, Amazon: https://youtu.be/jOqGMOGJQ1s?t=17
–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625
Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php
Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109
–
class Solution {
public:
int rep[1007];
int Find(int v) {
if (rep[v] != v)
rep[v] = Find(rep[v]);
return rep[v];
}
void Union(int u, int v) {
int a = Find(u);
int b = Find(v);
rep[a] = b;
}
int minCostConnectPoints(vector<vector<int>>& points) {
vector<pair<int, pair<int, int>>> kraw;
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
int d = abs(points[i][0] - points[j][0])
+ abs(points[i][1] - points[j][1]);
kraw.push_back({d, {i, j}});
}
}
sort(kraw.begin(), kraw.end());
for (int i = 0; i < points.size(); ++i)
rep[i] = i;
int wynik = 0;
for (int i = 0; i < kraw.size(); ++i) {
int d = kraw[i].first;
int u = kraw[i].second.first;
int v = kraw[i].second.second;
if (Find(u) != Find(v)) {
wynik += d;
Union(u, v);
}
}
return wynik;
}
};
Kod C++ programu "Min Cost to Connect All Points", który jest omówiony w powyższym filmie i który otrzymuje 100%
–
Kod Python programu Min Cost to Connect All Points, który otrzymuje 100%:
class Solution: rep = [] def Find(self, v): if (self.rep[v] != v): self.rep[v] = self.Find(self.rep[v]) return self.rep[v] def Union(self, u, v): a = self.Find(u) b = self.Find(v) self.rep[a] = b def minCostConnectPoints(self, points: List[List[int]]) -> int: self.rep = [i for i in range(len(points))] kraw = [] for i in range(len(points)): for j in range(i+1, len(points)): d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) kraw.append([d, i, j]) kraw.sort() wynik = 0 for d, u, v in kraw: if (self.Find(u) != self.Find(v)): wynik += d self.Union(u, v) return wynik