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