并查集
LeetCode
2 minutes read (About 277 words)

并查集

labuladong

通用模板，路径压缩

应用场景

  • 克鲁斯卡尔最小生成树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    template <class T>
    class UF {
    public:
        // n 为图中节点的个数
        explicit UF(int n)
        {
            count_ = n;
            parent_ = new T[n];
            for (T i = 0; i < n; i++) {
                parent_[i] = i;
            }
        }

        // 将节点 p 和节点 q 连通
        void Union(T p, T q) {
            T rootP = Find(p);
            T rootQ = Find(q);

            if (rootP == rootQ) {
                return;
            }

            parent_[rootQ] = rootP;
            // 两个连通分量合并成一个连通分量
            count_--;
        }

        // 判断节点 p 和节点 q 是否连通
        bool Connected(T p, T q) {
            T rootP = Find(p);
            T rootQ = Find(q);
            return rootP == rootQ;
        }

        // 返回图中的连通分量个数
        [[nodiscard]] int Count() const {
            return count_;
        }

        // 返回节点 x 的连通分量根节点
    private:
        T Find(T x) {
            while (parent_[x] != x) {
                // 进行路径压缩
                parent_[x] = parent_[parent_[x]];
                x = parent_[x];
            }
            return x;
        }
        // 连通分量个数
        int count_;
        // 存储每个节点的父节点
        T* parent_;
    };

990. 等式方程的可满足性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        int n = equations.size();
        UF<int> uf(26);
        for (const auto& eq :equations) {
            if (eq.substr(1, 2) == "==") {
                uf.Union(eq[0] - 'a', eq[3] - 'a');
            }
        }

        for (const auto& eq :equations) {
            if (eq.substr(1, 2) == "!=") {
                if (uf.Connected(eq[0] - 'a', eq[3] - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }
};
岛屿问题
LeetCode
5 minutes read (About 765 words)

岛屿问题

labuladong

200. 岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j, int m, int n) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i - 1, j, m, n);
        dfs(grid, i + 1, j, m, n);
        dfs(grid, i, j - 1, m, n);
        dfs(grid, i, j + 1, m, n);
    }
    int numIslands(vector<vector<char>>& grid) {
        int result = 0;
        int m = grid.size();
        int n= grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return result;
    }
};

1254. 统计封闭岛屿的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return;
        }
        if (grid[i][j] == 1) {
            return;
        }
        grid[i][j] = 1;
        dfs(grid, i - 1, j, m, n);
        dfs(grid, i + 1, j, m, n);
        dfs(grid, i, j - 1, m, n);
        dfs(grid, i, j + 1, m, n);
    }
    int closedIsland(vector<vector<int>>& grid) {
        int result = 0;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0, m, n);
            dfs(grid, i, n - 1, m, n);
        }
        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i, m, n);
            dfs(grid, m - 1, i, m, n);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    result++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return result;
    }
};

1020. 飞地的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return;
        }
        if (grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        dfs(grid, i - 1, j, m, n);
        dfs(grid, i + 1, j, m, n);
        dfs(grid, i, j - 1, m, n);
        dfs(grid, i, j + 1, m, n);
    }

    int numEnclaves(vector<vector<int>>& grid) {
        int result = 0;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0, m, n);
            dfs(grid, i, n - 1, m, n);
        }
        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i, m, n);
            dfs(grid, m - 1, i, m, n);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result += (grid[i][j] == 1);
            }
        }
        return result;
    }
};

695. 岛屿的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxArea = 0;
    int dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return 0;
        }
        if (grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        return dfs(grid, i - 1, j, m, n) + dfs(grid, i + 1, j, m, n) + dfs(grid, i, j - 1, m, n) + dfs(grid, i, j + 1, m, n) + 1;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = max(maxArea, dfs(grid, i, j, m, n));
                }
            }
        }
        return maxArea;
    }
};

1905. 统计子岛屿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool dfs(const vector<vector<int>>& grid1, vector<vector<int>>& grid2, int i, int j, int m, int n) {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return true;
        }
        if (grid2[i][j] == 0) {
            return true;
        }
        if (grid1[i][j] == 0) {
            return false;
        }
        grid2[i][j] = 0;
        bool a = dfs(grid1, grid2, i - 1, j, m, n);
        bool b = dfs(grid1, grid2, i + 1, j, m, n);
        bool c = dfs(grid1, grid2, i, j - 1, m, n);
        bool d = dfs(grid1, grid2, i, j + 1, m, n);
        return a && b && c && d;
    }

    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int result = 0;
        int m = grid1.size();
        int n = grid1[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid1[i][j] && grid2[i][j]) {
                    result += dfs(grid1, grid2, i, j, m, n);
                }
            }
        }
        return result;
    }
};

694. 不同的岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int numDistinctIslands(int[][] grid) {

    int m = grid.length, n = grid[0].length;

    // 记录所有岛屿的序列化结果

    HashSet<String> islands = new HashSet<>();

    for (int i = 0; i < m; i++) {

        for (int j = 0; j < n; j++) {

            if (grid[i][j] == 1) {

                // 淹掉这个岛屿，同时存储岛屿的序列化结果

                StringBuilder sb = new StringBuilder();

                // 初始的方向可以随便写，不影响正确性

                dfs(grid, i, j, sb, 666);

                islands.add(sb.toString());

            }

        }

    }

    // 不相同的岛屿数量

    return islands.size();

}
Follow

Links

Categories

Tag Cloud

Algorithm Algorithms BFS Binary Tree Binary enumerate C++ C/C++ Clion DAG图 DFS DataFrame Database Gradient Decent Methods Hexo LIS Latex Linear Regression LinkedList Map Markdown Matlab Polynomial Regression Postgis Postgresql Python Sorting Stack Union Find Week-contest Wireless communications git leetcode linux 内存管理 函数指针 多线程 并查集 拓扑排序 括号匹配 线段树

Recent

Archives

Tags

Algorithm 26
Algorithms 1
BFS 7
Binary Tree 1
Binary enumerate 1
C++ 6
C/C++ 3
Clion 1
DAG图 1
DFS 1
DataFrame 1
Database 2
Gradient Decent Methods 2
Hexo 1
LIS 1
Latex 1
Linear Regression 1
LinkedList 1
Map 1
Markdown 1
Matlab 2
Polynomial Regression 1
Postgis 1
Postgresql 2
Python 6
Sorting 2
Stack 1
Union Find 1
Week-contest 11
Wireless communications 1
git 1
leetcode 2
linux 1
内存管理 1
函数指针 1
多线程 1
并查集 1
拓扑排序 1
括号匹配 1
线段树 1

Recent

Archives

Tags

Algorithm 26
Algorithms 1
BFS 7
Binary Tree 1
Binary enumerate 1
C++ 6
C/C++ 3
Clion 1
DAG图 1
DFS 1
DataFrame 1
Database 2
Gradient Decent Methods 2
Hexo 1
LIS 1
Latex 1
Linear Regression 1
LinkedList 1
Map 1
Markdown 1
Matlab 2
Polynomial Regression 1
Postgis 1
Postgresql 2
Python 6
Sorting 2
Stack 1
Union Find 1
Week-contest 11
Wireless communications 1
git 1
leetcode 2
linux 1
内存管理 1
函数指针 1
多线程 1
并查集 1
拓扑排序 1
括号匹配 1
线段树 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×