搞定大厂算法面试之leetcode精讲23.并查集

2021-12-07 07:50:50 浏览数 (1)

搞定大厂算法面试之leetcode精讲23.并查集

视频讲解（高效学习）:点击学习
目录：

1.开篇介绍

2.时间空间复杂度

3.动态规划

4.贪心

5.二分查找

6.深度优先&广度优先

7.双指针

8.滑动窗口

9.位运算

10.递归&分治

11剪枝&回溯

12.堆

13.单调栈

14.排序算法

15.链表

16.set&map

17.栈

18.队列

19.数组

20.字符串

21.树

22.字典树

23.并查集

24.其他类型题

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

Find：确定元素属于哪一个子集，他可以被用来确定两个元素是否属于同一个子集，加入路径压缩，复杂度近乎O(1)

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

代码语言：javascript复制
//     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.dfs
  • 思路：循环网格，深度优先遍历每个坐标的四周，注意坐标不要越界，遇到陆地加1，并沉没四周的陆地，这样就不会重复计算
  • 复杂度：时间复杂度O(mn), m和n是行数和列数。空间复杂度是O(mn),最坏的情况下所有网格都需要递归，递归栈深度达到m * n

js：

代码语言：javascript复制
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)
}

java：

代码语言：javascript复制
class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r   1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c   1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr;   r) {
            for (int c = 0; c < nc;   c) {
                if (grid[r][c] == '1') {
                      num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}
方法2.bfs
  • 思路：循环网格，广度优先遍历坐标的四周，遇到陆地加1，沉没四周的陆地，不重复计算陆地数
  • 复杂度：时间复杂度O(mn),m和n是行数和列数。空间复杂度是O(min(m，n)),队列的长度最坏的情况下需要能容得下m和n中的较小者

js:

代码语言：javascript复制
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]) //四周的节点加入队列
        }
    }
}

java:

代码语言：javascript复制
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr;   r) {
            for (int c = 0; c < nc;   c) {
                if (grid[r][c] == '1') {
                      num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc   c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc   col);
                            grid[row-1][col] = '0';
                        }
                        if (row   1 < nr && grid[row 1][col] == '1') {
                            neighbors.add((row 1) * nc   col);
                            grid[row 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc   col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col   1 < nc && grid[row][col 1] == '1') {
                            neighbors.add(row * nc   col 1);
                            grid[row][col 1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
}
方法3.并查集
  • 思路：
  • 复杂度：时间复杂度O(mn)，时间复杂度其实是O(mn * f(mn))，f是采用并查集路径压缩时的复杂度，为常数，所以可以忽略。 m和n是行数和列数。空间复杂度是O(mn),并查集的空间

js:

代码语言：javascript复制
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()  //返回并查集的个数减一就行
};

Java:

代码语言：javascript复制
class Solution {
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m;   i) {
                for (int j = 0; j < n;   j) {
                    if (grid[i][j] == '1') {
                        parent[i * n   j] = i * n   j;
                          count;
                    }
                    rank[i * n   j] = 0;
                }
            }
        }

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

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx]  = 1;
                }
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr;   r) {
            for (int c = 0; c < nc;   c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc   c, (r-1) * nc   c);
                    }
                    if (r   1 < nr && grid[r 1][c] == '1') {
                        uf.union(r * nc   c, (r 1) * nc   c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc   c, r * nc   c - 1);
                    }
                    if (c   1 < nc && grid[r][c 1] == '1') {
                        uf.union(r * nc   c, r * nc   c   1);
                    }
                }
            }
        }

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

js

代码语言：javascript复制
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);//递归遍历
      }
  }
};

java:

代码语言：javascript复制
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int rows = isConnected.length;
        boolean[] visited = new boolean[rows];
        int count = 0;
        for (int i = 0; i < rows; i  ) {
            if (!visited[i]) {
                dfs(isConnected, visited, rows, i);
                count  ;
            }
        }
        return count;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int rows, int i) {
        for (int j = 0; j < rows; j  ) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, rows, j);
            }
        }
    }
}
方法2.bfs
  • 思路：广度优先遍历，循矩阵，然后寻找相邻城市加入队列，队列不为空就不断出队，继续遍历
  • 复杂度：时间复杂度O(n^2)，n是城市的数量，遍历矩阵中的每个元素。空间复杂度O(n)，队列和visited数组最长是n

js:

代码语言：javascript复制
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;
};

Java:

代码语言：javascript复制
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int rows = isConnected.length;
        boolean[] visited = new boolean[rows];
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < rows; i  ) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    for (int k = 0; k < rows; k  ) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                count  ;
            }
        }
        return count;
    }
}
方法3.并查集
  • 思路：循环矩阵，遇到相邻的城市就合并，最后返回并查集中集合的数量
  • 复杂度：时间复杂度O(n^2)，n是城市的数量，需要遍历矩阵，经过路径压缩后的并查集中需找父节点复杂度是常数级。空间复杂度是O(n)，即parent的空间

js:

代码语言：javascript复制
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();
};

Java:

代码语言：javascript复制
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int rows = isConnected.length;
        int[] parent = new int[rows];
        for (int i = 0; i < rows; i  ) {
            parent[i] = i;
        }
        for (int i = 0; i < rows; i  ) {
            for (int j = i   1; j < rows; j  ) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < rows; i  ) {
            if (parent[i] == i) {
                count  ;
            }
        }
        return count;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}
腾讯广告算法大赛

0 人点赞