用javascript分类刷leetcode23.并查集(图文视频讲解)

并查集(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][c] === '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();
};

视频讲解:传送门

0 条评论
请不要发布违法违规有害信息,如发现请及时举报或反馈
还没有人评论呢,速度抢占沙发!
相关文章
  • 前言经常会有人问,作为前端,你在实际工作中用到过哪些算法,而我回答一般是,树和位运算;想想 webpack 上的那些依赖的版本类型,想想 react 源码中的那些 flag 的定义和运算,我觉得还是很...

  • 递归三要素递归函数以及参数递归终止条件递归单层搜索逻辑递归伪代码模版:function recursion(level, param1, param2, ...) { //递归终止条件 if ...

  • 简介文中所有题目均为精心挑选过的超高频题目,所以大家可以收藏起来适用人群针对有一定数据结构基础(了解链表, 二叉树, 二叉堆, 递归)的基本概念,并对时间空间复杂度有基本认知的。食用指南将文中列出的每...

  • 首先需要了解链表的概念先把 next 记录下来无论是插入,删除,还是翻转等等操作,先把 next 指针用临时变量保存起来,这可以解决 90% 重组链表中指向出错的问题,如果不知道什么时候需要用到守卫,...

  • 工作太忙没有时间刷算法题,面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题,整理的内容有点长,建议先收藏,慢慢消化,在来年顺利拿到满意的offer。1、[LeetCode] 两数之...

  • 前言学习算法的时候,总会有一些让人生畏的名词,比方动态规划,贪心算法 等,听着就很难;而这一 part 就是为了攻破之前一直没有系统学习的 贪心算法;有一说一,做了这些贪心题,其实并没觉得发现了什么套...

  • 1. 栈是什么?一种先进后出的数据结构;JavaScript没有栈的结构;可以用array实现栈的功能入栈 push(x);出栈 pop();const stack = []; // 入栈 sta...

  • 什么是树一种分层数据的抽象模型。前端工作中常见的树包括:DOM树,级联选择,树形控件JS中没有树,可以用Object和Array构建树树的常用操作:深度/广度优先遍历,先中后序遍历深度优先遍历访问根节...

  • 1. 字典简介与集合类似,字典也是一种存储唯一值的数据结构,但它是以键值对的形式来存储。使用 ES6 Map1.1 字典的常用操作const m = new Map(); // 增 m.set('a...

  • 一、前言  《JavaScript刷LeetCode拿offer-双指针技巧》中,简单地介绍了双指针技巧相比较单指针的优点,以及结合 Easy 难度的题目带大家进一步了解双指针的应用。  进入 Med...

  • 什么是贪心算法贪心法,又称贪心算法,贪婪算法,在对问题求解时,总是做出在当前看来最好的选择,期望通过每个阶段的局部最优选择达到全局最优,但结果不一定最优适用场景:简单的说,问题能够分解成子问题来解决,...

  • 各类题的解决方案话不多说,系统整理下解题的一些算法和解决方案二叉树二叉树大多使用递归的方式左右两个元素向下递归。比如:计算二叉树最大深度var maxDepth = function (root) {...

  • 什么是动态规划动态规划,英文:Dynamic Programming,简称DP,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解...

  • 前言并查集是合并集合的方式,对于一些关联性的集合,合并查询的方式可以使得题目分类处理,是一种题型的解决方案,这里最关键是构思好集合之间的关联关系;在这一 part 中,仅仅只是对部分题做了了解学习,远...

  • 一、链表链表(Linked List)是一种常见的基础数据结构,也是线性表的一种。一个线性表是 n 个具有相同特性的数据元素的有限序列,线性表的存储结构分为两类:顺序表(数组)和链表。链表相比较顺序表...

  • 位运算基础:程序中所有的数载计算机内存中都是以二进制存储的,位运算就是直接对整数在内存中的二进制进行操作,由于直接在内存中进行操作,不需要转成十进制,因此处理速度非常快常见位运算x & 1 === 0...

  • 一、前言  本篇主要介绍双指针技巧的第二类题型:对数组进行预处理之后,再采用双指针遍历。  在 Medium 难度的题目中,此类问题可以归纳为 K-Sum 问题:两数之和:【881. 救生艇】;三数之...

  • 前言博主最近在刷leetcode,做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍历来完成的,因此写下这篇文章,记录一下二叉树层序遍历这件"神器"在实战的运用。[leetcode] 10...

  • 前言今天没啥前言,分治很难,主要难在如何拆分后比较好治理合并,这比二分这些只要拆了就结束要难上一个 level,所以这里属于出入 分治 这种想法的思维,后续会尽可能的锻炼这样的做法;做一道分治,如果能...

  • 序章我们把字符串、数组、正则、排序、递归归为简单算法。接下来系列里,将系列文章里将为大家逐一介绍。字符串翻转字符串中的单词给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初...