3 篇博文含有标签「并查集」

LCR 118.冗余连接

2022年1月27日 · 阅读需 5 分钟

1、题干

树可以看成是一个连通且无环的无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [a_i, b_i] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例 1：

输入: edges = [[1,2],[1,3],[2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
输出: [1,4]

提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

注意：本题与主站 684 题相同： https://leetcode-cn.com/problems/redundant-connection/

并查集还没学会，只能先用树和图的思想解题

2、解题思路

在树的概念中，叶子结点是指没有子结点的结点，叶子节点只跟父节点存在关联，即只有1条边。如果某个节点下只有叶子节点，把该节点下的所有叶子节点都移除掉之后它自己就变成了叶子节点。如果循环往复地移除树的所有叶子节点，最终这棵树的节点数会变为0 。

如果按题目意思在树中添加一条边，这棵树会变成一个有环图，而在移除所有叶子节点的操作中，环上的所有节点都不会被移除，本题就是利用这个结论解题。

总体思路 ：循环往复地移除树上所有的叶子节点，直到不存在叶子节点，最后遍历找到环中最后出现的边。

大体步骤 ：

先用矩阵建立节点关联关系，记为 matrix
- matrix 是一维数组，下标表示节点值
- matrix 中的元素是哈希集合，集合中包含与当前节点关联的所有节点
遍历 matrix 并把当前节点加入队列 queue 中，进行叶子节点的判断与移除
- 若该节点是叶子节点，则双向移除该节点与父节点的关联关系，同时把父节点加入队列 queue 中进行下一轮处理
- 若该节点不是叶子节点则跳过
最后遍历二维数组 edges 并在 matrix 中查找出处于环上且序号最大的边

3、代码

var findRedundantConnection = function (edges) {
    const n = edges.length, matrix = new Array(n + 1).fill(0);

    for (const [i, j] of edges) {
        !matrix[i] ? (matrix[i] = new Set([j])) : matrix[i].add(j);
        !matrix[j] ? (matrix[j] = new Set([i])) : matrix[j].add(i);
    }

    for (let k = 1; k <= n; k++) {
        const queue = [k];

        for (const i of queue) {
            if (matrix[i].size !== 1) continue;

            const j = matrix[i].keys().next().value;
            matrix[i].delete(j), matrix[j].delete(i);
            queue.push(j);
        }
    }

    return edges.reduce((a, [i, j]) => (matrix[i].size > 1 && matrix[j].size > 1 ? [i, j] : a), null);
};

4、复杂度

时间复杂度： $O(nlogn)$ ，复杂度比较高的代码在双层循环剪叶子那一段，外层循环 $n$ 次，内层循环最多为树的高度 $logn$ 次
空间复杂度： $O(n)$

5、执行结果

执行用时: 68 ms
内存消耗: 42.1 MB

剑指 Offer II 118.多余的边

2022年1月27日 · 阅读需 5 分钟

Whilconn

1、题干

树可以看成是一个连通且无环的无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [a_i, b_i] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例 1：

输入: edges = [[1,2],[1,3],[2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
输出: [1,4]

提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

注意：本题与主站 684 题相同： https://leetcode-cn.com/problems/redundant-connection/

并查集还没学会，只能先用树和图的思想解题

2、解题思路

在树的概念中，叶子结点是指没有子结点的结点，叶子节点只跟父节点存在关联，即只有1条边。如果某个节点下只有叶子节点，把该节点下的所有叶子节点都移除掉之后它自己就变成了叶子节点。如果循环往复地移除树的所有叶子节点，最终这棵树的节点数会变为0 。

如果按题目意思在树中添加一条边，这棵树会变成一个有环图，而在移除所有叶子节点的操作中，环上的所有节点都不会被移除，本题就是利用这个结论解题。

总体思路 ：循环往复地移除树上所有的叶子节点，直到不存在叶子节点，最后遍历找到环中最后出现的边。

大体步骤 ：

先用矩阵建立节点关联关系，记为 matrix
- matrix 是一维数组，下标表示节点值
- matrix 中的元素是哈希集合，集合中包含与当前节点关联的所有节点
遍历 matrix 并把当前节点加入队列 queue 中，进行叶子节点的判断与移除
- 若该节点是叶子节点，则双向移除该节点与父节点的关联关系，同时把父节点加入队列 queue 中进行下一轮处理
- 若该节点不是叶子节点则跳过
最后遍历二维数组 edges 并在 matrix 中查找出处于环上且序号最大的边

3、代码

var findRedundantConnection = function (edges) {
    const n = edges.length, matrix = new Array(n + 1).fill(0);

    for (const [i, j] of edges) {
        !matrix[i] ? (matrix[i] = new Set([j])) : matrix[i].add(j);
        !matrix[j] ? (matrix[j] = new Set([i])) : matrix[j].add(i);
    }

    for (let k = 1; k <= n; k++) {
        const queue = [k];

        for (const i of queue) {
            if (matrix[i].size !== 1) continue;

            const j = matrix[i].keys().next().value;
            matrix[i].delete(j), matrix[j].delete(i);
            queue.push(j);
        }
    }

    return edges.reduce((a, [i, j]) => (matrix[i].size > 1 && matrix[j].size > 1 ? [i, j] : a), null);
};

4、复杂度

时间复杂度： $O(nlogn)$ ，复杂度比较高的代码在双层循环剪叶子那一段，外层循环 $n$ 次，内层循环最多为树的高度 $logn$ 次
空间复杂度： $O(n)$

5、执行结果

执行用时: 68 ms
内存消耗: 42.1 MB

200.岛屿数量

2021年12月13日 · 阅读需 2 分钟

Whilconn

1、题干

给你一个由 '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
grid[i][j] 的值为 '0' 或 '1'

解题思路

遍历矩阵grid，以grid[i][j]为起点往上下左右4个方向进行深度遍历
深度遍历过程中需要注意2点
- 遍历过的节点修改为0，即grid[i][j] = '0'，以免重复遍历
- grid[i][j]必须在矩阵中且grid[i][j] === '1'才累加岛屿数量

代码

var numIslands = function (grid) {
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return false;
        grid[i][j] = '0';
        for (const [di, dj] of dirs) dfs(i + di, j + dj);
        return true;
    }

    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (dfs(i, j)) count++;
        }
    }

    return count;
};

1、题干​

2、解题思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

2、解题思路​

3、代码​

4、复杂度​

5、执行结果​

1、题干​

解题思路​

代码​

1、题干

2、解题思路

3、代码

4、复杂度

5、执行结果

1、题干

2、解题思路

3、代码

4、复杂度

5、执行结果

1、题干

解题思路

代码