企业官网建设流程全解析

卡二卡四无卡国产网站,建设银行 福建 招聘网站,营销型网站建设哪里好,wordpress python导入数据库本次围绕并查集的核心概念、实现方法、习题应用展开讨论#xff0c;明确了并查集的实际使用场景与解题思路#xff0c;以下是详细总结内容。一、 核心内容总结#xff08;一#xff09;并查集的定义与应用场景定义#xff1a;并查集是一种抽象数据类型#xff08;ADT明确了并查集的实际使用场景与解题思路以下是详细总结内容。一、 核心内容总结一并查集的定义与应用场景定义并查集是一种抽象数据类型ADT专门用于处理n 个不同元素的不相交集合的合并Union与查询Find问题能高效管理元素的所属集合关系。应用场景适用于需要动态维护集合归属、判断元素是否同属一个集合的场景。例如公司校招学生组队从互不相识的小分队合并为朋友圈、城市连通性省份划分、变量等式 / 不等式关系校验等。二并查集的数组表示方式并查集的底层通常采用一维数组实现利用数组下标与值的映射关系存储集合信息具体规则如下初始化将元素进行唯一编号后数组初始值全部设为-1数组下标对应元素编号如parent[0]对应元素 0。数值含义若数组值为负数该下标是当前集合的根节点负号仅表示 “根”数字的绝对值表示集合中元素的个数如parent[2] -5表示元素 2 是根节点对应集合有 5 个元素。若数组值为非负数该下标对应的元素不是根节点值表示其父节点在数组中的下标如parent[3] 2表示元素 3 的父节点是元素 2。三并查集的核心操作实现并查集的核心是查找Find和合并Union基于这两个操作可延伸出 “判断是否同集”“统计集合个数” 等功能查找根节点从目标元素出发不断向上查找其父节点直到找到值为负数的根节点若输入下标为负数抛出异常因为元素编号为非负。判断是否同集分别查找两个元素的根节点若根节点相同则同属一个集合否则不属于。合并两个集合先找到两个元素的根节点若根节点不同则进行合并将一个根节点的值更新为两个根节点值之和另一个根节点的父节点指向该根节点。统计集合个数遍历数组统计其中负数的个数每个负数对应一个根节点即一个集合。四典型习题解题思路会议讲解了两道并查集经典习题核心是将实际问题转化为集合的合并与查询省份数量问题问题描述给定 n 个城市的相连关系矩阵矩阵中i行j列1表示第 i 个城市和第 j 个城市直接相连求省份的数量省份是由直接 / 间接相连的城市组成的集合。解题思路遍历矩阵若matrix[i][j]1则将城市 i 和城市 j 合并遍历完成后统计并查集数组中负数的个数即为省份数量。等式方程的可满足性问题问题描述给定由变量关系字符串组成的数组方程形式为ab或a!b判断所有方程是否能同时成立。解题思路分两步处理第一步遍历所有方程将等号连接的变量合并到同一集合第二步遍历所有!方程检查不等号连接的变量是否在同一集合若在则方程不成立返回false否则返回true。二、重难点分析与通俗注释一重点 1并查集数组的数值含义难点根节点与普通节点的数值区别核心要点数组的下标是元素的 “身份证号”值是元素的 “归属信息”。通俗注释可以把集合想象成 “家族”根节点是 “族长”。数组值为负数时这个元素是族长数字的绝对值是家族人数数组值为正数时这个元素是家族成员值是族长的 “身份证号”或上一级成员的身份证号。比如parent[5] 3表示元素 5 的上级是元素 3parent[3] -4表示元素 3 是族长家族有 4 个人。二重点 2查找根节点的逻辑可拓展路径压缩优化提升效率核心要点查找的终点是根节点值为负数基础版查找是线性遍历优化版可通过 “路径压缩” 让元素直接指向根节点。通俗注释就像找族长基础版是 “你问你爸→爸问爷爷→爷爷问族长”要走好几步路径压缩是 “你直接记下班族长的手机号”下次找族长直接联系不用再层层询问效率更高。三重点 3合并两个集合的核心规则难点根节点的合并而非普通节点核心要点合并的是两个集合的根节点不是普通元素合并时要将一个根节点的父节点指向另一个根节点并更新集合大小。通俗注释两个家族合并只能是族长之间商量合并不能让家族里的普通成员说了算。比如 A 家族族长是 3家族有 5 人B 家族族长是 7家族有 3 人合并后可以让 7 的父节点是 3同时 3 的值变为-853表示合并后的家族有 8 人。四重点 4实际问题转化为并查集问题的思路难点如何将业务场景映射为集合的合并与查询核心要点先明确问题中的 “元素” 是什么再确定 “哪些元素需要合并为一个集合”最后通过查询 / 统计集合数解决问题。通俗注释比如省份数量问题“元素” 是城市“两个城市相连” 就是 “合并两个元素”“省份数量” 就是 “集合的个数”等式方程问题“元素” 是变量a、b 等“ab” 是 “合并 a 和 b”“a!b” 是 “查询 a 和 b 是否不同集”。三、Java 代码实现带详细注释以下代码采用 Java 实现包含并查集基础类、优化类路径压缩 按秩合并以及两道经典习题的解题代码。一并查集基础类基础版java运行/** * 并查集基础实现类线性查找未优化合并 */ public class UnionFind { private int[] parent; /** * 构造方法初始化并查集 * param n 元素个数 */ public UnionFind(int n) { // 初始化并查集数组初始值全为-1 parent new int[n]; for (int i 0; i n; i) { parent[i] -1; } } /** * 查找元素x的根节点基础版线性查找 * param x 目标元素 * return 根节点下标 * throws IllegalArgumentException 输入下标非法时抛出 */ public int find(int x) { if (x 0 || x parent.length) { throw new IllegalArgumentException(元素下标超出范围); } // 循环查找父节点直到找到根节点值为负数 while (parent[x] 0) { x parent[x]; } return x; } /** * 判断元素x和y是否在同一集合 * param x 元素x * param y 元素y * return true同集false不同集 */ public boolean isSameSet(int x, int y) { return find(x) find(y); } /** * 合并元素x和y所在的集合 * param x 元素x * param y 元素y */ public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { // 已在同一集合无需合并 return; } // 合并规则将rootY的父节点设为rootX更新rootX的集合大小 parent[rootX] parent[rootY]; parent[rootY] rootX; } /** * 统计集合的个数 * return 集合数量 */ public int getSetCount() { int count 0; for (int val : parent) { if (val 0) { count; } } return count; } }二并查集优化类路径压缩 按秩合并效率更高java运行/** * 并查集优化实现类路径压缩 按秩合并 */ public class UnionFindOptimized { private int[] parent; private int[] rank; // 存储集合的高度秩 /** * 构造方法初始化并查集 * param n 元素个数 */ public UnionFindOptimized(int n) { // parent数组初始值为自身根节点指向自己 parent new int[n]; // rank数组初始值为1每个集合的高度初始为1 rank new int[n]; for (int i 0; i n; i) { parent[i] i; rank[i] 1; } } /** * 查找元素x的根节点路径压缩迭代版避免递归栈溢出 * param x 目标元素 * return 根节点下标 * throws IllegalArgumentException 输入下标非法时抛出 */ public int find(int x) { if (x 0 || x parent.length) { throw new IllegalArgumentException(元素下标超出范围); } // 路径压缩将x的父节点直接设为根节点 if (parent[x] ! x) { parent[x] find(parent[x]); // 递归版路径压缩简洁小数据量推荐 // 迭代版路径压缩大数据量推荐避免栈溢出 /* int root x; // 先找到根节点 while (parent[root] ! root) { root parent[root]; } // 路径压缩将沿途节点的父节点都设为根节点 while (parent[x] ! root) { int temp parent[x]; parent[x] root; x temp; } return root; */ } return parent[x]; } /** * 判断元素x和y是否在同一集合 * param x 元素x * param y 元素y * return true同集false不同集 */ public boolean isSameSet(int x, int y) { return find(x) find(y); } /** * 合并元素x和y所在的集合按秩合并小秩合并到大秩下 * param x 元素x * param y 元素y */ public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并高度小的集合合并到高度大的集合下保持树的高度最小 if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else { // 高度相同合并后高度1 parent[rootY] rootX; rank[rootX]; } } /** * 统计集合的个数 * return 集合数量 */ public int getSetCount() { int count 0; for (int i 0; i parent.length; i) { // 根节点的特征是parent[i] i if (parent[i] i) { count; } } return count; } }三习题 1省份数量java运行/** * 省份数量问题求解 */ public class ProvinceCount { /** * 求解省份数量 * param isConnected 城市的相连关系矩阵 * return 省份数量 */ public static int findCircleNum(int[][] isConnected) { int n isConnected.length; // 初始化并查集这里用优化版也可用基础版 UnionFindOptimized uf new UnionFindOptimized(n); // 遍历矩阵仅遍历上三角避免重复合并 for (int i 0; i n; i) { for (int j i 1; j n; j) { if (isConnected[i][j] 1) { uf.union(i, j); } } } // 返回集合个数即省份数量 return uf.getSetCount(); } // 测试用例 public static void main(String[] args) { int[][] testMatrix {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}; System.out.println(省份数量 findCircleNum(testMatrix)); // 输出2 } }四习题 2等式方程的可满足性java运行/** * 等式方程的可满足性问题求解 */ public class EquationPossible { /** * 判断等式方程是否可满足 * param equations 等式/不等式数组 * return true可满足false不可满足 */ public static boolean equationsPossible(String[] equations) { // 变量是小写字母共26个映射为0-25的下标 UnionFindOptimized uf new UnionFindOptimized(26); // 第一步处理所有方程合并变量 for (String eq : equations) { if (eq.charAt(1) ) { // 字符转下标a-0b-1...z-25 int x eq.charAt(0) - a; int y eq.charAt(3) - a; uf.union(x, y); } } // 第二步处理所有!方程检查是否同集 for (String eq : equations) { if (eq.charAt(1) !) { int x eq.charAt(0) - a; int y eq.charAt(3) - a; if (uf.isSameSet(x, y)) { return false; } } } // 所有检查通过返回True return true; } // 测试用例 public static void main(String[] args) { String[] testEquations1 {ab, b!a}; System.out.println(equationsPossible(testEquations1)); // 输出false String[] testEquations2 {ab, bc, ac}; System.out.println(equationsPossible(testEquations2)); // 输出true } }