日日操av加勒比,91色老久久精品偷偷,亚洲成人精品久久久

寫在前：并查集是一種樹型的數(shù)據(jù)結(jié)構，用于處理一些不交集（Disjoint Sets）的合并及查詢問題。有一個聯(lián)合-查找算法（Union-find Algorithm）定義了兩個用于此數(shù)據(jù)結(jié)構的操作：

Find（查找）：確定元素屬于哪一個子集。它可以被用來確定兩個元素是否屬于同一子集。
Union（合并）：將兩個子集合并成同一個集合。

ps：這里的集合也可叫連通塊（連通分量），典型應用解決連通分量問題。

并查集解決單個問題（添加，合并，查找）的時間復雜度都是O(1)，可以應用在在線算法中。

路徑壓縮算法：即查找過程，最理想的情況就是所有點的代表節(jié)點都是相同，一共就是兩級結(jié)構。做法就是在查找時找到根之后把自身的值修改成根的下標，可以通過遞歸和迭代實現(xiàn)。

路徑壓縮

1.冗余連接（684 - 中）

題目描述：在本問題中, 樹指的是一個連通且無環(huán)的無向圖。輸入一個圖，該圖由一個有著N個節(jié)點 (節(jié)點值不重復1, 2, ..., N) 的樹及一條附加的邊構成。附加的邊的兩個頂點包含在1到N中間，這條附加的邊不屬于樹中已存在的邊。結(jié)果圖是一個以邊組成的二維數(shù)組。每一個邊的元素是一對[u, v] ，滿足 u < v，表示連接頂點u 和v的無向圖的邊。

返回一條可以刪去的邊，使得結(jié)果圖是一個有著N個節(jié)點的樹。如果有多個答案，則返回二維數(shù)組中最后出現(xiàn)的邊。答案邊 [u, v] 應滿足相同的格式 u < v。

示例 :

輸入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
解釋: 給定的無向圖為:
5 - 1 - 2
    |   |
    4 - 3

思路：樹是一個連通并無環(huán)的無向圖，如果一棵樹有 N個節(jié)點，則這棵樹有 N-1條邊。初始化N個節(jié)點，每個節(jié)點屬于不同的集合。

可以通過并查集尋找附加的邊，本質(zhì)是檢測圖的環(huán)。如果邊的兩個節(jié)點已經(jīng)出現(xiàn)在同一個集合里（在合并之前已經(jīng)連通），說明著邊的兩個節(jié)點已經(jīng)連在一起了，如果再加入這條邊一定就出現(xiàn)環(huán)了，記錄并返回。

代碼實現(xiàn)：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length + 1;
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.ans;
    }
}

class UnionFind {
    int[] roots;
    int[] ans = new int[2];  // 存放結(jié)果集

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        if (i != roots[i]) {
            roots[i] = find(roots[i]);
        }
        return roots[i];
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        } else {
            ans[0] = p;
            ans[1] = q;
        }
    }
}

2.省份數(shù)量（547 - 中）

題目描述：有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。省份是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。返回矩陣中省份的數(shù)量（城市群）。

示例 :

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

思路：并查集解法（單獨寫一個并查集類）

圖的頂點數(shù)為 n，則初始化 n 個單頂點集合，每個集合指向自身。
然后遍歷圖中的每個頂點，將當前頂點與其鄰接點進行合并。
最終結(jié)果返回合并后的集合的數(shù)量即可。

代碼實現(xiàn)：

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        // 初始化n個單頂點集合，
        UnionFind uf = new UnionFind(n);
        // 遍歷一半矩陣（兩個城市単連接即可），遇到1連接兩個城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.size;
    }
}

class UnionFind {
    int[] roots;   // 記錄每個省份的核心城市
    int size;   // 集合的數(shù)量

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        size = n;
    }
    // 尋找當前城市所在省份（城市群）的核心城市
    public int find(int i) {
        //若當前城市不是核心城市，則遞歸更新（類似樹結(jié)構）
        if (i != roots[i]) {
            roots[i] = find(roots[i]);
        }
        return roots[i];
    }
    // 將兩個城市連接到一個省份
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        // 當兩個城市的核心城市不同時，連接并更新核心城市，集合數(shù)量-1；若兩個城市在同一省份則不減
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            size--;
        }
    }
}

3.被圍繞的區(qū)域（130 - 中）

題目描述：給你一個 m x n 的矩陣 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充，返回填充后的矩陣。

示例 :

輸入：board = [["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"]]
解釋：被圍繞的區(qū)間不會存在于邊界上，換句話說，任何邊界上的 'O' 都不會被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會被填充為 'X'。如果兩個元素在水平或垂直方向相鄰，則稱它們是“相連”的。

思路：本題中O本質(zhì)就是兩大類：一種可以連通到邊界，一種不能連通到邊界（需要X覆蓋）。

并查集就是解決一種分類（連通性）問題的。對于每個節(jié)點我們用行數(shù)和列數(shù)生成id進行標識（用于下一步）。
遍歷每個O節(jié)點，上下左右四個方向進行合并：定義dummy節(jié)點區(qū)分上述兩大分類（將連通到邊界的與dummy進行合并）。
- 如果當前O在邊界，先與dummy節(jié)點合并
- 否則將當前點與上下左右O進行合并
再遍歷矩陣，只需要判斷O節(jié)點是否與dummy節(jié)點連通，如不連通則替換為X。

代碼實現(xiàn)：

class Solution {
    int row, col;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        row = board.length;
        col = board[0].length;
        int dummy = row * col;  // 虛擬分類點
        UnionFind uf = new UnionFind(row * col + 1);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    //當前節(jié)點在邊界就和 dummy 合并
                    if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                        uf.union(dummy, node(i, j));
                    } else {
                        //將上下左右的 O 節(jié)點和當前節(jié)點合并
                        if (board[i - 1][j] == 'O') uf.union(node(i, j), node(i - 1, j));
                        if (board[i][j - 1] == 'O') uf.union(node(i, j), node(i, j - 1));
                        if (board[i + 1][j] == 'O') uf.union(node(i, j), node(i + 1, j));
                        if (board[i][j + 1] == 'O') uf.union(node(i, j), node(i, j + 1));
                    }
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (uf.isConnected(node(i, j), dummy)) {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    int node(int i, int j) {
        return i * col + j;
    }
}

class UnionFind {
    int[] roots;

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }
    
    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        }
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}

ps：這里并查集的效率有點低。

4.島嶼的數(shù)量（200 - 中）

題目描述：給你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網(wǎng)格的四條邊均被水包圍。

示例 :

輸入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
輸出：1

思路：使用并查集計算集合（島嶼）的數(shù)量。對于陸地情況可以上下左右進行查找。類似547省份數(shù)量，用size變量保存連通分量的數(shù)量

注意：最終size = 連通塊的個數(shù) + 水的元素個數(shù)

故在遍歷每個元素的時候，統(tǒng)計水的個數(shù)（0的個數(shù)）
島嶼數(shù)量 = size - 水的個數(shù)

代碼實現(xiàn)：

class Solution {
    public int row, col;
    public int numIslands(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        int n = row * col;
        int ocean = 0;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    ocean += 1;
                } else {
                    if (i > 0 && grid[i - 1][j] == '1') uf.union(node(i, j), node(i - 1, j));
                    if (j > 0 && grid[i][j - 1] == '1') uf.union(node(i, j), node(i, j - 1));
                    if (i < row - 1 && grid[i + 1][j] == '1') uf.union(node(i, j), node(i + 1, j));
                    if (j < col - 1 && grid[i][j + 1] == '1') uf.union(node(i, j), node(i, j + 1));
                }
            }
        }
        return uf.size - ocean;
    }
    int node (int i, int j) {
        return i * col + j;
    }
}

class UnionFind {
    int[] roots;
    int size;   // 島嶼數(shù)量

    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        size = n;
    }

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] =roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            size--;
        }
    }
}

5.移除最多的同行或同列石頭（947 - 中）

題目描述：如果想移除一個石頭，那么它所在的行或者列必須有其他石頭存在。我們能移除的最多石頭數(shù)是多少？也就是說，只有一個石頭在連通分量中，才能被移除。對于連通分量而言，最理想的狀態(tài)是只剩一塊石頭。對于任何容量為n（n>1）一個連通分量，可以移除的石頭數(shù)都為n-1。

示例 :

輸入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
輸出：3
解釋：一種移除 3 塊石頭的方法如下所示：
1. 移除石頭 [2,2] ，因為它和 [2,0] 同行。
2. 移除石頭 [2,0] ，因為它和 [0,0] 同列。
3. 移除石頭 [0,2] ，因為它和 [0,0] 同行。
石頭 [0,0] 和 [1,1] 不能移除，因為它們沒有與另一塊石頭同行/列。

思路：本題注意理解我們要刪除最多的石頭（最后返回值），為此我們將所有的行和列進行連接呢？

在圖上構建若干個集合，每個集合可以看成一個鑰匙串，最后每個鑰匙串至少剩下一個鑰匙。一個核心（盡可能多刪除）
并查集里的元素是 描述「橫坐標」和「縱坐標」的數(shù)值。
假設有M個集合，設總結(jié)點數(shù)為N，那么顯而易見，我們能夠刪除的總結(jié)點數(shù)，也即move數(shù)為：move = N - M；

在原始的輸入中，行標號和列標號是共用的[1,n]區(qū)間內(nèi)的數(shù)字，導致行值和列值重復，無法達到我們完成并查集的結(jié)點連接的目的。

根據(jù)題目給出的數(shù)據(jù)范圍，單個坐標數(shù)值小于10000。
將列值映射到[10000,10000+n]的區(qū)間內(nèi)，這樣我們就獲得了所有節(jié)點的標號。

代碼實現(xiàn)：

class Solution {
    public int removeStones(int[][] stones) {
        int size = stones.length;
        // 題目給的數(shù)值在0 -10000，0-10000給橫坐標，10001-20002留給縱坐標
        UnionFind uf = new UnionFind(20002);
        for (int i = 0; i < size; i++) {
            uf.union(stones[i][0], stones[i][1] + 10001);
        }

        // 統(tǒng)計集合個數(shù)（即roots數(shù)量），由于行列為同一roots，故統(tǒng)計一個即可
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < size; i++) {
            set.add(uf.find(stones[i][0]));
        }
        // 總石頭數(shù)量 - roots數(shù)量 == 最多可以刪除的節(jié)點數(shù)
        return size - set.size();
    }
}

class UnionFind {
    int[] roots;
    
    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
        }
    }
}

6.連通網(wǎng)絡的操作次數(shù)（1319 - 中）

題目描述：用以太網(wǎng)線纜將 n 臺計算機連接成一個網(wǎng)絡，計算機的編號從 0 到 n-1。線纜用 connections 表示，其中 connections[i] = [a, b] 連接了計算機 a 和 b。

網(wǎng)絡中的任何一臺計算機都可以通過網(wǎng)絡直接或者間接訪問同一個網(wǎng)絡中其他任意一臺計算機。

給你這個計算機網(wǎng)絡的初始布線 connections，你可以拔開任意兩臺直連計算機之間的線纜，并用它連接一對未直連的計算機。請你計算并返回使所有計算機都連通所需的最少操作次數(shù)。如果不可能，則返回 -1 。

示例 :

輸入：n = 4, connections = [[0,1],[0,2],[1,2]]
輸出：1
解釋：拔下計算機 1 和 2 之間的線纜，并將它插到計算機 1 和 3 上。

思路：最終實現(xiàn)目標：將所有網(wǎng)絡連接成同一個網(wǎng)絡。類似547省份問題。注意兩個問題：

線要夠，即n個節(jié)點至少需要n-1條線
三個連通塊至少需要兩個邊（即需要兩條多余的線），問題轉(zhuǎn)化為：最少操作數(shù)（多余線纜）= 連通塊數(shù)量 - 1

代碼實現(xiàn)：

class Solution {
    public int makeConnected(int n, int[][] connections) {
        int num = connections.length;
        if (num < n - 1) return -1;  // 線不夠
        UnionFind uf = new UnionFind(n);
        
        for (int[] connection : connections) {
            uf.union(connection[0], connection[1]);
        }
        return uf.count - 1;   
    }
}

class UnionFind {
    int[] roots;
    int count;  // 記錄連通塊的數(shù)量
    
    public UnionFind(int n) {
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        count = n;  
    }

    public int find(int i) {
        while (i != roots[i]) {
            roots[i] = roots[roots[i]];
            i = roots[i];
        }
        return i;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            roots[pRoot] = qRoot;
            count--;   
        }
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Leetcode --- 并查集相關題目

Leetcode --- 并查集相關題目

1.冗余連接（684 - 中）

2.省份數(shù)量（547 - 中）

3.被圍繞的區(qū)域（130 - 中）

4.島嶼的數(shù)量（200 - 中）

5.移除最多的同行或同列石頭（947 - 中）

6.連通網(wǎng)絡的操作次數(shù)（1319 - 中）

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Leetcode --- 并查集相關題目

1.冗余連接（684 - 中）

2.省份數(shù)量（547 - 中）

3.被圍繞的區(qū)域（130 - 中）

4.島嶼的數(shù)量（200 - 中）

5.移除最多的同行或同列石頭（947 - 中）

6.連通網(wǎng)絡的操作次數(shù)（1319 - 中）

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av