leetcode算法
并查集 其实并查集顾名思义，并就是有“合并集合”，查就是“查找集合中的元素”。
主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两 种操作：
1 2 合并（Union）：把两个不相交的集合合并为一个集合。 查询（Find）：查询两个元素是否在同一个集合中
既然是集合，自然集合中可能会有很多的元素，有多个集合时怎么区分集合呢？并查集的重要思想在于，用集合中的一个元素来代表集合。
并查集在网络连通性问题、渗滤、图像处理、最近公共祖先、有限状态自动机的等价性、Kruskal 的最小生成树算法等等都有非常广的应用。
(LeetCode- 128) 最长连续序列 题目 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
1 2 3 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
1 2 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
分析 方法: 并查集 可以用并查集来解决，基本思想是让一个连续区间内的元素都会 在一个集合中，且这些元素的根结点都为连续区间内最远的右边界元素。
回顾一下我们学习并查集的概念的时候，可以看到对并查集的操作无非就是 初始化并查集、查找并查集中的元素和合并集合，所以具体思路则可以：
遍历所有元素，对于遇到的元素 num，如果 num+1 存在，将 num 加入到 num+1 所在的集合中；
重新遍历一遍所有元素 num，通过 find 函数找到 num 所在集合的根结点， 也就是 num 所在连续区间内最远的右边界，从而求得连续区间的长度。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 public class LongestConsecutive { public static void main(String[] args) { int[] nums = {100,4,200,1,3,2}; int i = new LongestConsecutive().longestConsecutive(nums); System.out.println(""); } public int longestConsecutive(int[] nums) { ADT adt = new ADT(nums); int ans = 0; for(int num : nums){ // 当 num + 1 存在， 将num合并到num+1所在的集合中 if(adt.find(num + 1) != null){ adt.union(num, num + 1); } } // 找到数组中每个元素num所在连续区间内最远的右边界。 取最大的那个 for(int num : nums){ int right = adt.find(num); ans = Math.max(ans, right - num + 1); } return ans; } class ADT{ // 记录每个节点的父节点，key为当前节点，value为父节点 private Map<Integer, Integer> parent; public ADT(int[] nums){ parent = new HashMap<>(); // 初始化并查集，每个节点的父节点为自身 for(int num : nums){ parent.put(num, num); } } // 查找x的父节点 public Integer find(int x){ // nums 不包含 x if(!parent.containsKey(x)){ return null; } // 遍历找到x 的父节点 // x ！= parent.get(x) 说明x有父节点 集合中只有根节点的父节点是自己，这是退出循环 while (x != parent.get(x)){ // 路径压缩， parent.get(x) 找到x的父节点 // parent.get(parent.get(x)) 找到x 的父节点的父节点， 也就是祖父节点 parent.put(x, parent.get(parent.get(x))); // 从x最新的父节点出发， 继续往上寻找知道根节点为止 x = parent.get(x); } return x; } // 合并两个集合， 将x 并入 y 的连续区间中 public void union(int x, int y){ int rootX = find(x); int rootY = find(y); // x和y已经处于同一连续区间中 if(rootX == rootY){ return; } parent.put(rootX, rootY); } } }
(LeetCode- 200) 岛屿数量 题目 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
1 2 3 4 5 6 7 输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
示例 2：
1 2 3 4 5 6 7 输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
分析 方法
这个题目既可以用并查集来解决，因为这是个考察连通性的问题；也可以看 成一个无向图，用广度或深度优先搜索来解决。
站在并查集的角度，水平方向和/或竖直方向上相邻的 1 构成一个集合，然后看看二维网格里有多个这样的集合。所以同样可以遵循初始化并查集、查找并查集中的元素和合并集合这几步来解决。
整体思路： 初始时将每一个“1”的格子看作一个岛。然后遍历整个格，考察该格子右侧和下侧的格子，如果是“1”，将其合并到当前格子所在的岛中，每次合并都累计合并次数。岛屿数量就是最初单个格子岛屿数量减去合并次数。
当然这里用图论中的广度或深度优先搜索速度会更快些，等我们学习完图论后，可以再回来看看这个题怎么用广度或深度优先搜索解决。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 public class NumIslands { public static void main(String[] args) { char[][] grid = {{'1', '1', '1','1','0'}, {'1', '1', '0','1','0'},{'1', '1', '0','0','0'},{'0', '0', '0','0','0'} }; int i = new NumIslands().numIslands(grid); System.out.println(""); } // 初始化岛屿数量 int isLandCount = 0; // 累计合并次数 int mergedCount = 0; // 并查集实现 public int numIslands(char[][] grid) { int m = grid.length, n = grid[0].length; ADT uf = new ADT(grid); // 遍历原始数组中的每个元素 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ // 二维转一维时， 在一维数组中的下标 int landx = i * n + j; if(grid[i][j] == '1'){ // 检测右侧是否联通，联通则要合并 if(j < n - 1 && grid[i][j + 1] == '1'){ uf.union(landx, landx + 1); } // 检测下侧是否联通， 联通则要合并 if(i < m - 1 && grid[i + 1][j] == '1'){ uf.union(landx, landx + n); } } } } return isLandCount - mergedCount; } class ADT{ // 存储每个元素的父节点 private int[] parents; /* 原始数组元素为二维char, 转为一维int rank的作用记录每个节点的子树深度 因为在两棵树合并时， 把小树合并到大树上，可以让每个元素到根节点的距离最少 * */ private int[] rank; public ADT(char[][] grid){ int m = grid.length, n = grid[0].length; this.parents = new int[m * n]; this.rank = new int[m * n]; // 遍历原始数组， 累计初始数量，并初始化一维数组parents和rank for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if (grid[i][j] == '1') { isLandCount++; int k = i * n + j; parents[k] = k; rank[k] = 1; } } } } // 带路径压缩的查找根节点 public int find(int x){ // 集合中只有根节点的父节点是自己 if(parents[x] == x) return x; // 数自然可以递归处理， 并且在查询的过程中不断变更节点的父节点，以缩短查找路径 return parents[x] = find(parents[x]); } // 合并集合 public void union(int x, int y){ int xRoot = find(x); int yRoot = find(y); // x 和 y 的根节点不一致， 进行集合合并 if(xRoot != yRoot){ // 合并次数 + 1 mergedCount++; // 把小树合并到大树上 if(rank[yRoot] <= rank[xRoot]) parents[yRoot] = xRoot; else parents[xRoot] = yRoot; // 两颗数深度一样， 合并后数的深度要加 1 if(rank[xRoot] == rank[yRoot]) rank[xRoot]++; } } } }
(LeetCode- 399) 除法求值 题目 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：
1 2 3 4 5 6 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000] 解释： 条件：a / b = 2.0, b / c = 3.0 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：
1 2 入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] 输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
1 2 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
分析 方法
这个题目题干非常复杂，解答代码量也很多，但其实如果搞明白了并查集的 三件事：初始化、查找和合并，题目并不能算很难处理。
说到底 queries[j] = [Cj, Dj] 能否有答案，其实就是考察 Cj, Dj 能否归属于同一 个集合，或者说 Cj, Dj 能否通过 equations 连通起来。但是我们前面的题目中只 需要记录两个元素是否属于同一个集合即可，这个题目中还需要记录 equations 中的变量对之间的倍数关系，我们把这个倍数关系称为权值。
初始化的时候，所有的元素单独成为集合，并且权值为 1。然后按照变量对 数组 equations 和实数值数组 values 进行集合合并，并更新权值。
接下来处理问题数组 queries，检查 Cj, Dj 是否处于同一集合，并且进行路 径压缩。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 public class CalcEquation { public static void main(String[] args) { List<List<String>> equations = new LinkedList<>(); List<String> equations1 = new ArrayList<>(); equations1.add("a"); equations1.add("b"); equations.add(equations1); List<String> equations2 = new ArrayList<>(); equations2.add("b"); equations2.add("c"); equations.add(equations2); double[] values = {2.0,3.0}; List<List<String>> queries = new LinkedList<>(); List<String> queries1 = new ArrayList<>(); queries1.add("a"); queries1.add("c"); queries.add(queries1); List<String> queries2 = new ArrayList<>(); queries2.add("b"); queries2.add("a"); queries.add(queries2); List<String> queries3 = new ArrayList<>(); queries3.add("a"); queries3.add("e"); queries.add(queries3); List<String> queries4 = new ArrayList<>(); queries4.add("a"); queries4.add("a"); queries.add(queries4); List<String> queries5 = new ArrayList<>(); queries5.add("x"); queries5.add("x"); queries.add(queries5); double[] doubles = new CalcEquation().calcEquation(equations, values, queries); System.out.println(""); } public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { int equationSize = equations.size(); ADT adt = new ADT(2 * equationSize); // 拆解equations中的变量对， 给每个变量赋一个单独的id， 方便并查集操作 Map<String, Integer> map = new HashMap<>(2 * equationSize); int id = 0; for(int i = 0; i < equationSize; i++){ List<String> eqution = equations.get(i); String first = eqution.get(0); String second = eqution.get(1); if(!map.containsKey(first)){ map.put(first, id); id++; } if(!map.containsKey(second)){ map.put(second, id); id++; } // 对变量对中的两个变量进行集合合并 adt.union(map.get(first), map.get(second),values[i]); } // 处理问题数组queries int queriesSize = queries.size(); double[] res = new double[queriesSize]; for(int i = 0; i < queriesSize; i++){ String var1 = queries.get(i).get(0); String var2 = queries.get(i).get(1); Integer id1 = map.get(var1); Integer id2 = map.get(var2); if(id1 == null || id2 == null){ res[i] = -1.0d; }else { res[i] = adt.calc(id1, id2); } } return res; } class ADT{ // 记录每个元素的父节点 private int[] parent; /*节点指向当前父节点时的权值， 因为存在路径压缩，所以父节点会变化， 权值自然也会变化*/ private double[] weight; public ADT(int n){ this.parent = new int[n]; this.weight = new double[n]; for(int i = 0; i < n; i++){ // 初始化， 每个元素都是自己的父节点， 权值为1 parent[i] = i; weight[i] = 1.0d; } } // 集合合并 public void union(int x, int y, double value){ int rootX = find(x); int rootY = find(y); // 两者不属于统一集合， 合并， 并更新权值 if(rootX != rootY){ parent[rootX] = rootY; weight[rootX] = weight[y] * value / weight[x]; } } // 带路径压缩的根节点查找， 并更新权值 public int find(int x){ if(x != parent[x]){ int origin = parent[x]; parent[x] = find(parent[x]); weight[x] = weight[x] * weight[origin]; } return parent[x]; } // public double calc(int x, int y){ int rootX = find(x); int rootY = find(y); if(rootX == rootY){ return weight[x] / weight[y]; }else { return -1.0d; } } } }