UnionFind

130.被围绕的区域

November 7, 20222 分钟阅读 Liubang LeetCode LeetCode UnionFind

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

解法一：并查集

这道题通常会用DFS来解，但是也可以用并查集解：首先我们将四条边上的’O’合并成一个连通分量，然后再将圈内的所有相邻的 ‘O’连接起来，最后遍历整个表，将所有为’O’且不与四条边上的’O’所在的连通分量相连的节点设置...

990.等式方程的可满足性

November 6, 20221 分钟阅读 Liubang LeetCode LeetCode UnionFind

题目描述

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程equations[i]的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

题解

这一道题，显然是用并查集来解决，思路很简单，由于相等具有传递性，可以认为，一开始所有的字母变量都是独立的集合，通过等式传递性，可以将这些相等的字母合并到同一个集合，最后看不等式中，是否存在连通的字母，如果存在则表示等式方程不满足条件。...

128.最长连续序列

November 5, 20221 分钟阅读 Liubang LeetCode LeetCode UnionFind

题目描述

给定一个未排序的整数数nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度O(n)的算法解决此问题。

解法一：并查集

这道题目可以用并查集来解决。初始状态下数组中的每个元素都是一个独立的集合，然后遍历数组，将当前元素相邻的元素合并到一个集合，最后返回所有集合中元素个数最多的数量。这里要注意去重。

#include <vector>
#include <unordered_map>

class UnionFind {
public:
    UnionFind(int num) {
        for (int i = 0; i <...