乐趣区

关于leetcode:用javascript分类刷leetcode23并查集图文视频讲解

jiezi

并查集（union & find）：用于解决一些元素的合并和查问问题

Find：确定元素属于哪一个子集，他能够被用来确定两个元素是否属于同一个子集，退出门路压缩，复杂度近乎 O(1)

Union：将两个子集合并成同一个汇合 

//                    0,1,2,3
//parent:        0,1,2,3
//size:         1,1,1,1
class UnionFind{constructor(n){ // 结构一个大小为 n 的汇合
        this.count = n
        this.parent = new Array(n)   
        this.size = new Array(n)  // size 数组记录着每棵树的大小
        for (let i = 0; i < n; i++) {this.parent[i] = i; // 本人是本人的 parent
            this.size[i] = 1;
        }
    }

    union(p,q){ // 连通结点 p 和结点 q, p 和 q 都是索引
        let rootP = this.find(p);
        let rootQ = this.find(q);
        if(rootP === rootQ) return
        // 元素数量小的接到数量多的上面，这样比拟均衡
        if (this.size[rootP] > this.size[rootQ]) {this.parent[rootQ] = rootP;
            this.size[rootP] += this.size[rootQ];
        } else {this.parent[rootP] = rootQ;
            this.size[rootQ] += this.size[rootP];
        }
        this.count--;
    }

    isConnected(p, q) { // 判断 p,q 是否连通
        return this.find(p)=== this.find(q) 
    }

    find(x) { // 找到 x 结点的 root
        while (this.parent[x] != x) {
            // 进行门路压缩
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    getCount() { // 返回子集个数
        return this.count;
    }
}

//                    0,1,2,3
//parent:        0,1,2,3
//rank:         1,1,1,1
// 采纳 rank 优化
class UnionFind {constructor(n) { // 结构一个节点数为 n 的汇合
        this.count = n // 并查集总数
        this.parent = new Array(n)
        this.rank = new Array(n)  // rank 数组记录着每棵树的分量
        for (let i = 0; i < n; i++) {this.parent[i] = i; // 本人是本人的 parent
            this.rank[i] = 1;    // 每个汇合上节点的数量
        }
    }

    union(p, q) { // 连通结点 p 和结点 q, p 和 q 都是索引
        let rootP = this.find(p);
        let rootQ = this.find(q);
        if (rootP === rootQ) return
        // 深度小的接在深度大元素下
        if (this.rank[rootP] > this.rank[rootQ]) {this.parent[rootQ] = rootP;
        } else if (this.rank[rootP] < this.rank[rootQ]) {this.parent[rootP] = rootQ;
        } else {this.parent[rootP] = rootQ;
            this.rank[rootQ]++
        }
        this.count--;
    }

    isConnected(p, q) { // 判断 p,q 是否连通
        return this.find(p) === this.find(q)
    }

    find(x) { // 找到 x 结点的 root
        while (this.parent[x] != x) {
            // 进行门路压缩
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    getCount() { // 返回子集个数
        return this.count;
    }
}

200. 岛屿数量 (medium)

给你一个由 ‘1’（海洋）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水突围，并且每座岛屿只能由程度方向和 / 或竖直方向上相邻的海洋连贯造成。

此外，你能够假如该网格的四条边均被水突围。

示例 1：

输出：grid = [
[“1″,”1″,”1″,”1″,”0”],
[“1″,”1″,”0″,”1″,”0”],
[“1″,”1″,”0″,”0″,”0”],
[“0″,”0″,”0″,”0″,”0”]
]
输入：1
示例 2：

输出：grid = [
[“1″,”1″,”0″,”0″,”0”],
[“1″,”1″,”0″,”0″,”0”],
[“0″,”0″,”1″,”0″,”0”],
[“0″,”0″,”0″,”1″,”1”]
]
输入：3

提醒：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
gridi 的值为 ‘0’ 或 ‘1’

动画过大，点击查看

办法 1.dfs
  • 思路：循环网格，深度优先遍历每个坐标的周围，留神坐标不要越界，遇到海洋加 1，并沉没周围的海洋，这样就不会反复计算
  • 复杂度：工夫复杂度 O(mn), m 和 n 是行数和列数。空间复杂度是 O(mn), 最坏的状况下所有网格都须要递归，递归栈深度达到 m * n

js：

const numIslands = (grid) => {
    let count = 0
    for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[0].length; j++) {// 循环网格
            if (grid[i][j] === '1') {// 如果为海洋，count++，count++
                turnZero(i, j, grid)
            }
        }
    }
    return count
}
function turnZero(i, j, grid) {// 沉没周围的海洋
    if (i < 0 || i >= grid.length || j < 0
        || j >= grid[0].length || grid[i][j] === '0') return // 查看坐标的合法性
    grid[i][j] = '0'// 让周围的海洋变为淡水
    turnZero(i, j + 1, grid)
    turnZero(i, j - 1, grid)
    turnZero(i + 1, j, grid)
    turnZero(i - 1, j, grid)
}
办法 2.bfs
  • 思路：循环网格，广度优先遍历坐标的周围，遇到海洋加 1，沉没周围的海洋，不反复计算海洋数
  • 复杂度：工夫复杂度 O(mn),m 和 n 是行数和列数。空间复杂度是 O(min(m，n)), 队列的长度最坏的状况下须要能容得下 m 和 n 中的较小者

js:

const numIslands = (grid) => {
    let count = 0
    let queue = []
    for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[0].length; j++) {if (grid[i][j] === '1') {
                count++
                grid[i][j] = '0' // 做标记，防止反复遍历
                queue.push([i, j]) // 退出队列
                turnZero(queue, grid)
            }
        }
    }
    return count
}
function turnZero(queue, grid) {const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    while (queue.length) {// 当队列中还有元素的时候 
        const cur = queue.shift() // 取出队首元素
        for (const dir of dirs) {// 四个方向广度优先扩散
            const x = cur[0] + dir[0]
            const y = cur[1] + dir[1]
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') {continue}// 查看坐标合法性
            grid[x][y] = '0' // 沉没海洋
            queue.push([x, y]) // 周围的节点退出队列
        }
    }
}
办法 3. 并查集
  • 思路：
  • 复杂度：工夫复杂度 O(mn)，工夫复杂度其实是 O(mn * f(mn))，f 是采纳并查集门路压缩时的复杂度，为常数，所以能够疏忽。m 和 n 是行数和列数。空间复杂度是 O(mn), 并查集的空间

js:

class UnionFind {constructor(n) { // 结构一个节点数为 n 的汇合
        this.count = n // 并查集总数
        this.parent = new Array(n)
        this.size = new Array(n)  // size 数组记录着每棵树的分量
        for (let i = 0; i < n; i++) {this.parent[i] = i; // 本人是本人的 parent
            this.size[i] = 1;    // 每个汇合上节点的数量
        }
    }

    union(p, q) { // 连通结点 p 和结点 q, p 和 q 都是索引
        let rootP = this.find(p);
        let rootQ = this.find(q);
        if (rootP === rootQ) return
        // 元素数量小的接到数量多的上面，这样比拟均衡
        if (this.size[rootP] > this.size[rootQ]) {this.parent[rootQ] = rootP;
            this.size[rootP] += this.size[rootQ];
        } else {this.parent[rootP] = rootQ;
            this.size[rootQ] += this.size[rootP];
        }
        this.count--;
    }

    isConnected(p, q) { // 判断 p,q 是否连通
        return this.find(p) === this.find(q)
    }

    find(x) { // 找到 x 结点的 root
        while (this.parent[x] != x) {
            // 进行门路压缩
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    getCount() { // 返回子集个数
        return this.count;
    }

}

var numIslands = function (grid) {
    let m = grid.length
    if (m === 0) return 0
    let n = grid[0].length
    const dummy = -1
    const dirs = [[1, 0], [0, 1]]// 方向数组 向右 向下
    const uf = new UnionFind(m * n)
    for (let x = 0; x < m; x++) {for (let y = 0; y < n; y++)
            if (grid[x][y] === '0') {// 如果网格是 0，则和 dummy 合并
                uf.union(n * x + y, dummy) 
            }
            else if (grid[x][y] === '1') {// 如果网格是 1，则向右 向下尝试
                for (let d of dirs) {let r = x + d[0]
                    let c = y + d[1]
                    if (r >= m || c >= n) continue // 坐标合法性
                    if (grid[r] === '1') { // 以后网格的左边 上面如果是 1，则和以后网格合并
                        uf.union(n * x + y, n * r + c)
                    }
                }
            }
    }
    return uf.getCount()  // 返回并查集的个数减一就行};

547. 省份数量 (medium)

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 间接相连，且城市 b 与城市 c 间接相连，那么城市 a 与城市 c 间接相连。

省份 是一组间接或间接相连的城市，组内不含其余没有相连的城市。

给你一个 n x n 的矩阵 isConnected，其中 isConnectedi = 1 示意第 i 个城市和第 j 个城市间接相连，而 isConnectedi = 0 示意二者不间接相连。

返回矩阵中 省份 的数量。

示例 1：

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

示例 2：

输出：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输入：3

提醒：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnectedi 为 1 或 0
isConnectedi == 1
isConnectedi == isConnectedj

办法 1.dfs
  • 思路：深度优先遍历，visited 记录是否拜访过，循环省份数组，递归寻找 isConnected 矩阵中相邻的城市。
  • 复杂度：工夫复杂度 O(n^2)，n 是城市的数量，遍历矩阵中的每个元素。空间复杂度 O(n)，递归深度不超过 n

js

var findCircleNum = function(isConnected) {
  const rows = isConnected.length;
  const visited = new Set();// 记录是否拜访过
  let count = 0;// 省份数量
  for (let i = 0; i < rows; i++) {if (!visited.has(i)) {// 如果没拜访过
          dfs(isConnected, visited, rows, i);// 深度优先遍历
          count++;// 省份数量 +1
      }
  }
  return count;
};

const dfs = (isConnected, visited, rows, i) => {for (let j = 0; j < rows; j++) {if (isConnected[i][j] == 1 && !visited.has(j)) {// 如果 i，j 相连接
          visited.add(j);
          dfs(isConnected, visited, rows, j);// 递归遍历
      }
  }
};
办法 2.bfs
  • 思路：广度优先遍历，循矩阵，而后寻找相邻城市退出队列，队列不为空就一直出队，持续遍历
  • 复杂度：工夫复杂度 O(n^2)，n 是城市的数量，遍历矩阵中的每个元素。空间复杂度 O(n)，队列和 visited 数组最长是 n

js:

var findCircleNum = function(isConnected) {
  const rows = isConnected.length;
  const visited = new Set();// 记录是否拜访过
  let count = 0;
  const queue = new Array();
  for (let i = 0; i < rows; i++) {if (!visited.has(i)) {// 没有拜访过
          queue.push(i); // 退出队列
          while (queue.length) {// 队列不为空 持续循环
              const j = queue.shift();// 出队
              visited.add(j);
              for (let k = 0; k < rows; k++) {// 循环相邻的城市 退出队列
                  if (isConnected[j][k] === 1 && !visited.has(k)) {queue.push(k);
                  }
              }
          }
          count++;
      }
  }
  return count;
};
办法 3. 并查集
  • 思路：循环矩阵，遇到相邻的城市就合并，最初返回并查集中汇合的数量
  • 复杂度：工夫复杂度 O(n^2)，n 是城市的数量，须要遍历矩阵，通过门路压缩后的并查集中需找父节点复杂度是常数级。空间复杂度是 O(n)，即 parent 的空间

js:

class UnionFind{constructor(n){ // 结构一个大小为 n 的汇合
        this.count = n
        this.parent = new Array(n)   
        this.size = new Array(n)  // size 数组记录着每棵树的大小
        for (let i = 0; i < n; i++) {this.parent[i] = i; // 本人是本人的 parent
            this.size[i] = 1;
        }
    }

    union(p,q){ // 连通结点 p 和结点 q, p 和 q 都是索引
        let rootP = this.find(p);
        let rootQ = this.find(q);
        if(rootP === rootQ) return
        // 元素数量小的接到数量多的上面，这样比拟均衡
        if (this.size[rootP] > this.size[rootQ]) {this.parent[rootQ] = rootP;
            this.size[rootP] += this.size[rootQ];
        } else {this.parent[rootP] = rootQ;
            this.size[rootQ] += this.size[rootP];
        }
        this.count--;
    }

    isConnected(p, q) { // 判断 p,q 是否连通
        return this.find(p)=== this.find(q) 
    }

    find(x) { // 找到 x 结点的 root
        while (this.parent[x] != x) {
            // 进行门路压缩
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    getCount() { // 返回子集个数
        return this.count;
    }
}


var findCircleNum = function(isConnected) {
    const rows = isConnected.length;
    const uf = new UnionFind(rows)

    for (let i = 0; i < rows; i++) {for (let j = i + 1; j < rows; j++) {if (isConnected[i][j] == 1) {// 相邻城市合并
                uf.union(i, j);
            }
        }
    }

    return uf.getCount();};

视频解说：传送门

退出移动版