템 플 릿 + 고전 문 제 를 찾 습 니 다.
4304 단어 데이터 구조
템 플 릿
class UnionFind{
public:
vector father;
UnionFind(int num){ //num
for(int i = 0; i < num; i++){
father.push_back(i); //
}
}
int Find(int n){
//
if(father[n] == n)
return n;
father[n] = Find(father[n]); //
return father[n];
}
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
};
고전 제목 1: leetcode 547. 모멘트
class UnionFind{
public:
vector father;
UnionFind(int num){
for(int i = 0; i < num; i++){
father.push_back(i);
}
}
int Find(int n){
if(father[n] == n)
return n;
father[n] = Find(father[n]);
return father[n];
}
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
};
class Solution {
public:
int findCircleNum(vector>& M) {
int N = M.size();
UnionFind UF(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(M[i][j]){
UF.Union(i, j);
}
}
}
int res = 0;
for(int i = 0; i < N; i++){
if(UF.Find(i) == i)
res++;
}
return res;
}
};
고전 제목 2: leetcode 200. 섬의 개수
class UnionFind{
public:
vector father;
UnionFind(int num){
for(int i = 0; i < num; i++){
father.push_back(i);
}
}
int Find(int n){
if(father[n] == n)
return n;
father[n] = Find(father[n]);
return father[n];
}
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
};
class Solution {
public:
int encode(int i, int j, int n){
return i * n + j;
}
int numIslands(vector>& grid) {
int M = grid.size();
if(M == 0)
return 0;
int N = grid[0].size();
if(N == 0)
return 0;
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
UnionFind UF(M * N);
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
if(grid[i][j] == '1'){
for(int d = 0; d < 4; d++){
int di = directions[d][0];
int dj = directions[d][1];
if(i + di >= 0 && i + di < M && j + dj >= 0 && j + dj < N && grid[i+di][j+dj] == '1'){
UF.Union(encode(i, j, N), encode(i + di, j + dj, N));
}
}
}
}
}
int res = 0;
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
if(grid[i][j] == '1' && UF.Find(encode(i, j, N)) == encode(i, j, N))
res++;
}
}
return res;
}
};
고전 제목 3: leetcode 684. 중복 연결
class UnionFind{
public:
vector father;
UnionFind(int num){
for(int i = 0; i < num; i++){
father.push_back(i);
}
}
int Find(int n){
if(father[n] == n)
return n;
father[n] = Find(father[n]);
return father[n];
}
bool Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
return fa == fb;
}
};
class Solution {
public:
vector findRedundantConnection(vector>& edges) {
int N = edges.size();
UnionFind UF(N + 1);
vector res(2, 0);
for(int i = 0; i < edges.size(); i++){
int u = edges[i][0];
int v = edges[i][1];
if(UF.Union(u, v)){
res[0] = u;
res[1] = v;
}
}
return res;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.