leetcode并查集刷题顺序

文章目录

- - - [128. 最长连续序列](https://leetcode-cn.com/problems/longest-consecutive-sequence/)
    - [130. 被围绕的区域](https://leetcode-cn.com/problems/surrounded-regions/)
    - [200. 岛屿数量](https://leetcode-cn.com/problems/number-of-islands/)
    - [684. 冗余连接](https://leetcode-cn.com/problems/redundant-connection/)
    - [685. 冗余连接 II](https://leetcode-cn.com/problems/redundant-connection-ii/)

128. 最长连续序列

难度困难331

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

class Solution {
public:
    struct UnionSet {
        int *fa, *cnt;
        UnionSet(int n) {
            fa = new int[n + 1];
            cnt = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
                cnt[i] = 1;
            }
        }
        bool isroot(int x) {
            return x == fa[x];
        }
        int get(int x) {
            return (fa[x] = (x == fa[x] ? x : get(fa[x])));
        }
        void merge(int a, int b) { 
            int aa = get(a), bb = get(b);
            if (aa == bb) return ;
            fa[aa] = bb;
            cnt[bb] += cnt[aa];
            return ;
        }
        ~UnionSet() {
            delete[] fa;
            delete[] cnt;
        }
    };

    int longestConsecutive(vector<int>& nums) {
        UnionSet u(nums.size());
        unordered_map<int, int> h;
        for (int i = 0; i < nums.size(); i++) {
            if (h.find(nums[i]) != h.end()) continue;
            if (h.find(nums[i] - 1) != h.end()) {
                u.merge(i, h[nums[i] - 1]);
            }
            if (h.find(nums[i] + 1) != h.end()) {
                u.merge(i, h[nums[i] + 1]);
            }
            h[nums[i]] = i;
        }
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (!u.isroot(i)) continue;
            ans = max(ans, u.cnt[i]);
        }
        return ans;
    }
};

130. 被围绕的区域

难度中等213

给定一个二维的矩阵，包含

'X'

和

'O'

（字母 O）。

找到所有被

'X'

围绕的区域，并将这些区域里所有的

'O'

用

'X'

填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的

'O'

都不会被填充为

'X'

。任何不在边界上，或不与边界上的

'O'

相连的

'O'

最终都会被填充为

'X'

。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

class Solution {
public:
    struct UnionSet {
        int *fa, *cnt;
        UnionSet(int n) {
            fa = new int[n + 1];
            cnt = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
                cnt[i] = 1;
            }
        }
        bool isroot(int x) {
            return x == fa[x];
        }
        int get(int x) {
            return (fa[x] = (x == fa[x] ? x : get(fa[x])));
        }
        void merge(int a, int b) { 
            int aa = get(a), bb = get(b);
            if (aa == bb) return ;
            fa[aa] = bb;
            cnt[bb] += cnt[aa];
            return ;
        }
        ~UnionSet() {
            delete[] fa;
            delete[] cnt;
        }
    };
    int n, m;
    int ind(int i, int j) {
        return (i * m) + j + 1;
    }
    void solve(vector<vector<char>>& board) {
        if (board.size() == 0) return ;
        n = board.size();
        m = board[0].size();
        UnionSet u(n * m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') continue;
                if (i && board[i - 1][j] == 'O') u.merge(ind(i, j), ind(i - 1, j));
                if (j && board[i][j - 1] == 'O') u.merge(ind(i, j), ind(i, j - 1));
                if (i == 0 || i == n - 1) u.merge(ind(i, j), 0);
                if (j == 0 || j == m - 1) u.merge(ind(i, j), 0);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') continue;
                if (u.get(ind(i, j)) == u.get(0)) continue;
                board[i][j] = 'X';
            }
        }
        return ;
    }
};

200. 岛屿数量

难度中等573

给你一个由

'1'

（陆地）和

'0'

（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

class Solution {
public:
    struct UnionSet {
        int *fa, *cnt;
        UnionSet(int n) {
            fa = new int[n + 1];
            cnt = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
                cnt[i] = 1;
            }
        }
        bool isroot(int x) {
            return x == fa[x];
        }
        int get(int x) {
            return (fa[x] = (x == fa[x] ? x : get(fa[x])));
        }
        void merge(int a, int b) { 
            int aa = get(a), bb = get(b);
            if (aa == bb) return ;
            fa[aa] = bb;
            cnt[bb] += cnt[aa];
            return ;
        }
        ~UnionSet() {
            delete[] fa;
            delete[] cnt;
        }
    };
    int n, m;
    int ind(int i, int j) {
        return (i * m) + j + 1;
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0) return 0;
        n = grid.size();
        m = grid[0].size();
        UnionSet u(n * m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') continue;
                if (i && grid[i - 1][j] == '1') u.merge(ind(i, j), ind(i - 1, j));
                if (j && grid[i][j - 1] == '1') u.merge(ind(i, j), ind(i, j - 1));
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') continue;
                if (!u.isroot(ind(i, j))) continue;
                ans += 1;
            }
        }
        return ans;
    }
};

684. 冗余连接

难度中等109

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以

边

组成的二维数组。每一个

边

的元素是一对

[u, v]

，满足

u < v

，表示连接顶点

和

的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边

[u, v]

应满足相同的格式

u < v

。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
  1
 / \
2 - 3

示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
    |   |
    4 - 3

注意:

输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。

class Solution {
public:
    struct UnionSet {
        int *fa;
        UnionSet(int n) {
            fa = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
            }
            return ;
        }
        int get(int x) {
            return (fa[x] = (x - fa[x] ? get(fa[x]) : x));
        }
        int merge(int a, int b) {
            if (get(a) == get(b)) return 0;
            fa[get(a)] = get(b);
            return 1;
        }
    };

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionSet u(edges.size());
        vector<int> ret;
        for (int i = 0; i < edges.size(); i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            if (u.merge(a, b)) continue;//联通时候
            ret.push_back(a);//不连通记录下来
            ret.push_back(b);//不连通记录下来
            break;
        }
        return ret;
    }
};

685. 冗余连接 II

难度困难62

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以

边

组成的二维数组。每一个

边

的元素是一对

[u, v]

，用以表示有向图中连接顶点

and

和顶点的边，其中父节点

是子节点

的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3

示例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

注意:

二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

class Solution {
public:
    struct UnionSet {
        int *fa, cnt;
        UnionSet(int n) {
            fa = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
            }
            cnt = n;
            return ;
        }
        int get(int x) {
            return (fa[x] = (x - fa[x] ? get(fa[x]) : x));
        }
        int merge(int a, int b) {
            if (get(a) == get(b)) return 0;
            cnt -= 1;
            fa[get(a)] = get(b);
            return 1;
        }
    }; 
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int indeg[edges.size() + 1];
        int outdeg[edges.size() + 1];
        int fa[edges.size() + 1];
        int vis[edges.size() + 1];
        memset(indeg, 0, sizeof(indeg));
        memset(outdeg, 0, sizeof(outdeg));
        memset(fa, 0, sizeof(fa));
        memset(vis, 0, sizeof(vis));
        int flag = -1;
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            indeg[v] += 1;
            outdeg[u] += 1;
            fa[v] = u; 
            if (indeg[v] == 2) flag = v;
        }
        if (flag != -1) {
            for (int i = edges.size() - 1; i >= 0; i--) {
                if (flag - edges[i][1]) continue;
                UnionSet u(edges.size());
                for (int j = 0; j < edges.size(); j++) {
                    if (i == j) continue;
                    u.merge(edges[j][0], edges[j][1]);
                }
                if (u.cnt != 1) continue;
                return edges[i];
            }
        }
        queue<int> q;
        for (int i = 1; i <= edges.size(); i++) {
            if (outdeg[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int ind = q.front();
            vis[ind] = 1;
            q.pop();
            outdeg[fa[ind]] -= 1;
            if (outdeg[fa[ind]] == 0) q.push(fa[ind]);
        }
        for (int i = edges.size() - 1; i >= 0; i--) {
            int u = edges[i][0];
            int v = edges[i][1];
            if (vis[u] || vis[v]) continue;
            return edges[i];
        }
        return edges[0]; // 没用的
    }
};

leetcode并查集刷题顺序

文章目录

128. 最长连续序列

130. 被围绕的区域

200. 岛屿数量

684. 冗余连接

685. 冗余连接 II

继续阅读

【leetcode】32.longest-valid-parentheses（最长有效括号）【leetcode】32.longest-valid-parentheses（最长有效括号）

力扣每日一题：65. 有效数字题目：65. 有效数字解题思路

<LeetCode>三道脑筋急转弯编程题

求水洼的问题——深度优先算法

200. 岛屿的个数（深度优先搜索）

dfs深度优先搜索_图的深度优先搜索（DFS）

【算法提高班】贪婪策略

#每日一题力扣第28题采购方案

【python】：布尔运算

对角线遍历LeetCode–对角线遍历

查找算法之二分查找查找算法之二分查找

LeetCode-110-平衡二叉树-C语言

笔试面试题目：滑动窗口(二)

27. Remove Element(列表)题目代码

LeetCode OJ Binary Tree Right Side View

leetcode809