LeetCode力扣——并查集：947. 移除最多的同行或同列石头,1971. 寻找图中是否存在路径，2424. 最长上传前缀

947. 移除最多的同行或同列石头

题目描述

947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

运行代码

class Solution {public int removeStones(int[][] stones) {int n = stones.length;List<Integer>[] adj = new List[n];boolean[] visited = new boolean[n];for (int i = 0; i < n; i++) {adj[i] = new ArrayList<>();}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (sameRowOrCol(stones[i], stones[j])) {adj[i].add(j);adj[j].add(i);}}}int remain = 0;for (int i = 0; i < n; i++) {if (!visited[i]) {remain++;explore(i, adj, visited);}}return n - remain;}private boolean sameRowOrCol(int[] a, int[] b) {return a[0] == b[0] || a[1] == b[1];}private void explore(int curr, List<Integer>[] adj, boolean[] visited) {if (visited[curr]) return;visited[curr] = true;for (int next : adj[curr]) {explore(next, adj, visited);}}
}

代码思路

一、整体功能

这段代码的目的是计算在给定二维平面上的一系列点（由整数坐标表示）中，可以移除的点的最大数量，使得剩下的点无法通过水平或垂直方向与其他点相连。

二、主要方法分析

removeStones方法：
- 将remain初始化为 0，用于记录最终剩下的无法通过水平或垂直方向与其他点相连的点的数量。
- 创建一个boolean[] visited数组，用于标记每个点是否被访问过。长度也为点的总数。
- 创建一个List<Integer>[] adj数组，用于存储每个点的相邻点列表。这个数组的长度与点的总数相同。
- n表示输入的二维数组stones的长度，也就是点的总数。
- 构建相邻点列表：通过两层嵌套循环遍历所有的点对。如果两个点在同一行或同一列（通过sameRowOrCol方法判断），则将它们互相添加到对方的相邻点列表中。
- 深度优先搜索计算剩余点的数量：通过循环遍历所有的点，如果一个点没有被访问过，则将remain加一，并从这个点开始进行深度优先搜索（调用explore方法）。最后返回可以移除的点的数量，即总点数n减去剩余点的数量remain。
sameRowOrCol方法：接收两个点的坐标数组a和b，判断这两个点是否在同一行（横坐标相同）或同一列（纵坐标相同），如果是则返回true，否则返回false。
explore方法：接收当前点的索引curr、相邻点列表数组adj和访问标记数组visited。如果当前点已经被访问过，则直接返回。将当前点标记为已访问。遍历当前点的相邻点列表，对每个未访问的相邻点递归调用explore方法进行深度优先搜索。

1971. 寻找图中是否存在路径

题目描述

1971. 寻找图中是否存在路径

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

运行代码

class Solution {public boolean validPath(int n, int[][] edges, int source, int destination) {int[] parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}for (int[] edge : edges) {union(edge[0], edge[1], parent);}return find(source, parent) == find(destination, parent);}private int find(int x, int[] parent) {return parent[x] == x? x : (parent[x] = find(parent[x], parent));}private void union(int x, int y, int[] parent) {int rootX = find(x, parent);int rootY = find(y, parent);if (rootX!= rootY) {parent[rootX] = rootY;}}
}

代码思路

validPath方法：
- 初始化变量：创建一个整数数组p，用于存储每个节点的父节点。这里使用了并查集的数据结构来判断节点之间的连通性。首先将数组p初始化为每个节点的父节点都是自身，表示每个节点最初都在不同的集合中。
- 合并节点集合：遍历输入的边列表edges，对于每条边[u, v]，通过调用find方法找到u和v的代表元素（即所在集合的根节点），然后将其中一个代表元素的父节点设置为另一个代表元素，实现两个集合的合并。
- 判断路径是否存在：最后，通过调用find方法找到源节点source和目标节点destination的代表元素，如果它们相同，则说明源节点和目标节点在同一个集合中，即存在一条路径连接它们，返回true；否则返回false。
find方法：
- 这个方法实现了并查集中的查找操作，用于找到一个节点所在集合的代表元素（根节点）。
- 如果一个节点的父节点就是它自己，那么它就是所在集合的代表元素，直接返回该节点。
- 如果一个节点的父节点不是它自己，那么递归地调用find方法找到它的父节点的代表元素，并在返回之前将该节点的父节点设置为找到的代表元素，这一步叫做路径压缩，可以加快后续的查找操作。

2424. 最长上传前缀

题目描述

2424. 最长上传前缀

给你一个 n 个视频的上传序列，每个视频编号为 1 到 n 之间的不同数字，你需要依次将这些视频上传到服务器。请你实现一个数据结构，在上传的过程中计算 最长上传前缀 。

如果 闭区间 1 到 i 之间的视频全部都已经被上传到服务器，那么我们称 i 是上传前缀。最长上传前缀指的是符合定义的 i 中的 最大值 。

请你实现 LUPrefix 类：

LUPrefix(int n) 初始化一个 n 个视频的流对象。
void upload(int video) 上传 video 到服务器。
int longest() 返回上述定义的 最长上传前缀 的长度。

运行代码

class LUPrefix {private int x;private java.util.Set<Integer> s;public LUPrefix(int n) {x = 1;s = new java.util.HashSet<>();}public void upload(int video) {s.add(video);}public int longest() {while (s.contains(x)) {x++;}return x - 1;}
}

代码思路

构造函数LUPrefix(int n)：初始化变量：将x初始化为 1，表示当前最长上传前缀的下一个期望视频编号。创建一个HashSet<Integer>类型的集合s，用于存储已经上传的视频编号。
upload(int video)方法：功能：这个方法用于将指定编号的视频标记为已上传，即将视频编号添加到集合s中。
longest()方法：
- 循环查找：通过一个while循环，不断检查当前的x是否在集合s中。如果在集合中，说明视频编号为x的视频已经上传，此时将x的值增加 1，继续检查下一个编号。
- 确定最长上传前缀：当x不在集合s中时，循环停止。此时x - 1就是最长上传前缀的长度。这是因为在循环停止时，x是第一个未上传的视频编号，所以最长上传前缀就是x - 1。