新手网站设计看哪本书,电子商务网站建设规划报告,上海高端网站定制开发,wordpress引入外部js文章目录 本节设置的意义并查集篇并查集简介以及常见技巧并查集板子(洛谷)情侣牵手问题相似的字符串组岛屿数量(并查集做法)省份数量移除最多的同行或同列石头最大的人工岛找出知晓秘密的所有专家 建图及其拓扑排序篇链式前向星建图板子课程表 本节设置的意义
主要就是为了复习… 文章目录 本节设置的意义并查集篇并查集简介以及常见技巧并查集板子(洛谷)情侣牵手问题相似的字符串组岛屿数量(并查集做法)省份数量移除最多的同行或同列石头最大的人工岛找出知晓秘密的所有专家 建图及其拓扑排序篇链式前向星建图板子课程表 本节设置的意义
主要就是为了复习图论算法, 尝试从题目解析的角度,更深入的理解图论算法…
并查集篇
并查集简介以及常见技巧
并查集是一种用于大集团查找, 合并等操作的数据结构, 常见的方法有
find: 用来查找元素在大集团中的代表元素(这里使用的是扁平化的处理)isSameSet: 用来查找两个元素是不是一个大集团的(其实就是find的应用)union: 用来合并两大集团的元素
关于并查集打标签的技巧, 其实我们之前的size数组也是一种打标签的逻辑, 其实打标签就是给每一个集团的代表节点打上标签即可, 还有我们在并查集的题目中通常会设置一个sets作为集合的总数目(每次合并–), 这是一个常见的技巧, 并查集的细节我们在这里不进行过多的介绍, 在之前的章节中有细致的描述…
并查集板子(洛谷)
这里我们的并查集的板子使用的是洛谷的板子(小挂大的优化都没必要其实)
// 并查集模版(洛谷)
// 本实现用递归函数实现路径压缩而且省掉了小挂大的优化一般情况下可以省略
// 测试链接 : https://www.luogu.com.cn/problem/P3367import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main{public static int MAXN 10001;public static int[] father new int[MAXN];public static int n;public static void build() {for (int i 0; i n; i) {father[i] i;}}public static int find(int i) {if (i ! father[i]) {father[i] find(father[i]);}return father[i];}public static boolean isSameSet(int x, int y) {return find(x) find(y);}public static void union(int x, int y) {father[find(x)] find(y);}public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in new StreamTokenizer(br);PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() ! StreamTokenizer.TT_EOF) {n (int) in.nval;build();in.nextToken();int m (int) in.nval;for (int i 0; i m; i) {in.nextToken();int z (int) in.nval;in.nextToken();int x (int) in.nval;in.nextToken();int y (int) in.nval;if (z 1) {union(x, y);} else {out.println(isSameSet(x, y) ? Y : N);}}}out.flush();out.close();br.close();}}
情侣牵手问题 本题的突破点就是如果一个大集团里面有 n 对情侣, 那么我们至少要交换 n - 1次(通过把情侣进行编号)
// 这次我们尝试使用轻量版的并查集来解决这道题
class Solution {private static final int MAX_CP 31;private static final int[] father new int[MAX_CP];private static int sets 0;private static int find(int i) {if (i ! father[i]) {father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b) {return find(a) find(b);}private static void union(int a, int b) {int fa find(a);int fb find(b);if (fa ! fb) {father[fa] fb;sets--;}}// 初始化并查集private static void build(int n) {for (int i 0; i n; i) {father[i] i;}sets n;}public int minSwapsCouples(int[] row) {build(row.length / 2);for (int i 0; i row.length; i 2) {int n1 row[i] / 2;int n2 row[i 1] / 2;union(n1, n2);}return row.length / 2 - sets;}
}相似的字符串组 其实就是枚举每一个位置, 然后判断是不是一组的就OK了
// 还是使用一下轻量级的并查集板子
class Solution {private static final int MAX_SZ 301;private static final int[] father new int[MAX_SZ];private static int sets 0;private static int find(int i) {if (i ! father[i]) {father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b) {return find(a) find(b);}private static void union(int a, int b) {int fa find(a);int fb find(b);if (fa ! fb) {father[fa] fb;sets--;}}// 初始化并查集private static void build(int n) {for (int i 0; i n; i) {father[i] i;}sets n;}public int numSimilarGroups(String[] strs) {build(strs.length);// 主流程的时间复杂度是 O(n ^ 2), 遍历strs的每一个位置int m strs[0].length();for (int i 0; i strs.length; i) {for (int j i 1; j strs.length; j) {// 获取到两个字符串, 然后计算两个字符串的不同字符数量String s1 strs[i];String s2 strs[j];int diff 0;for (int k 0; k m diff 3; k) {if (s1.charAt(k) ! s2.charAt(k))diff;}if (diff 0 || diff 2)union(i, j);}}return sets;}
}岛屿数量(并查集做法) 这道题的解法非常多, 比如多源 BFS , 洪水填充(其实就是递归加回溯) , 还有今天介绍的并查集的方法(这个方法不是最好的)
// 这个题的并查集做法只要注意一点就可以了: 把一个二维下标转化为一维下标
class Solution {private static final int MAX_SZ 301 * 301;private static final int[] father new int[MAX_SZ];private static int sets 0;private static int row 0;private static int col 0;// 模拟bfs的move数组private static final int[] move { -1, 0, 1, 0, -1 };private static int find(int i) {if (i ! father[i]) {father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b) {return find(a) find(b);}private static void union(int a, int b) {int fa find(a);int fb find(b);if (fa ! fb) {father[fa] fb;sets--;}}private static void build(char[][] grid, int rl, int cl) {row rl;col cl;sets 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if (grid[i][j] 1) {sets;father[getIndex(i, j)] getIndex(i, j);}}}}public int numIslands(char[][] grid) {// 初始化并查集并统计 1 的数量build(grid, grid.length, grid[0].length);// 遍历grid进行合并for (int i 0; i row; i) {for (int j 0; j col; j) {// 向四个方向扩展if (grid[i][j] 1) {for (int k 0; k 4; k) {int nx i move[k];int ny j move[k 1];if (nx 0 nx row ny 0 ny col grid[nx][ny] 1) {union(getIndex(i, j), getIndex(nx, ny));}}}}}return sets;}// 二维下标转一维下标private static int getIndex(int i, int j) {return i * col j;}
}省份数量 没什么可说的, 就是一个简单的并查集的思路
class Solution {// 这其实也是一个并查集的题private static final int MAXM 201;private static final int[] father new int[MAXM];private static final int[] size new int[MAXM];private static int sets 0;private static int find(int i){if(i ! father[i]){father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b){return find(a) find(b);}private static void union(int a, int b){if(!isSameSet(a, b)){int fa find(a);int fb find(b);if(size[fa] size[fb]){father[fb] fa;size[fa] size[fb];}else{father[fa] fb;size[fb] size[fa];}sets--;}}private static void build(int n){for(int i 0; i n; i){father[i] i;size[i] 1;}sets n;}public int findCircleNum(int[][] isConnected) {// 初始化并查集build(isConnected.length);for(int i 0; i isConnected.length; i){int[] info isConnected[i];for(int j 0; j info.length; j){if(info[j] 1){union(i, j);}}}return sets;}
}移除最多的同行或同列石头 其实就是每一个集团最后都会被消成一个元素, 我们中间用哈希表加了一些关于离散化的处理的技巧
// 使用一下轻量版本的并查集加上哈希表进行离散化的操作
class Solution {private static MapInteger, Integer rowFirst new HashMap();private static MapInteger, Integer colFirst new HashMap();private static final int MAXM 1001;private static final int[] father new int[MAXM];private static int sets 0;private static int find(int i){if(i ! father[i]){father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b){return find(a) find(b);}private static void union(int a, int b){int fa find(a);int fb find(b);if(fa ! fb){father[fa] fb;sets--;}}// 初始化并查集private static void build(int n){for(int i 0; i n; i){father[i] i;}sets n;}public int removeStones(int[][] stones) {// 清空哈希表rowFirst.clear();colFirst.clear();// 初始化并查集build(stones.length);for(int i 0; i stones.length; i){int row stones[i][0];int col stones[i][1];if(!rowFirst.containsKey(row)){rowFirst.put(row, i);}else{union(rowFirst.get(row), i);}if(!colFirst.containsKey(col)){colFirst.put(col, i);}else{union(colFirst.get(col), i);}}return stones.length - sets;}}最大的人工岛 本题注意的点就是, 首先我们二维的矩阵, 想要使用并查集, 需要先把二维的坐标转化为一维的坐标, 然后通过一维的坐标使用并查集, 首先把所有的岛进行合并, 然后来到一个 空位置 , 就尝试向四个方向进行扩展尝试进行岛屿的链接, 最后返回最大的连成一片的岛屿数量即可
/*** 本题我们是采用的并查集(轻量板子)的方法来做* 核心点就是首先使用 并查集 (二维下标转换一维下标) 进行人工岛的合并* 本题需要我们使用size的辅助信息, 因为 size 也相当于打标签的技巧* 然后枚举每一个位置进行岛屿的合并*/
class Solution {private static final int MAX_LEN 501;private static final int MAX_SIZE MAX_LEN * MAX_LEN;private static final int[] father new int[MAX_SIZE];private static final int[] size new int[MAX_SIZE];private static int len 0;private static final int[] move {-1, 0, 1, 0, -1};private static int find(int i){if(i ! father[i]){father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b){return find(a) find(b);}private static void union(int a, int b){if(!isSameSet(a, b)){int fa find(a);int fb find(b);if(size[fa] size[fb]){father[fb] fa;size[fa] size[fb];}else{father[fa] fb;size[fb] size[fa];}}}// 初始化并查集private static void build(int[][] grid){len grid.length;for(int i 0; i len; i){for(int j 0; j len; j){if(grid[i][j] 1){int index getIndex(i, j);father[index] index;size[index] 1;}}}}// 二维下标转换为一维下标private static int getIndex(int i, int j){return i * len j;}public int largestIsland(int[][] grid) {build(grid);int res 0;// 遍历矩阵进行合并for(int i 0; i len; i){for(int j 0; j len; j){if(grid[i][j] 1){// 此时向四周进行扩展合并for(int k 0; k 4; k){int nx i move[k];int ny j move[k 1];if(nx 0 nx len ny 0 ny len grid[nx][ny] 1){union(getIndex(i, j), getIndex(nx, ny));}} // 尝试进行人工岛最大面积的更新res Math.max(res, size[find(getIndex(i, j))]);}}}// 遍历所有的 0 位置, 尝试向四周进行枚举更新最大值// 创建一个map用来进行去重SetInteger set new HashSet();for(int i 0; i len; i){for(int j 0; j len; j){if(grid[i][j] 0){set.clear();int tempRes 1;// 向四周进行扩展然后尝试进行岛屿链接for(int k 0; k 4; k){int nx i move[k];int ny j move[k 1];if(nx 0 nx len ny 0 ny len grid[nx][ny] 1){int f find(getIndex(nx, ny));if(!set.contains(f)){tempRes size[f];set.add(f);}}}res Math.max(res, tempRes); }}}return res;}
}找出知晓秘密的所有专家 本题我们运用的是一种打标签的技巧, 还有就是注意的是并查集如何进行拆解, 其实就是修改一下father数组的内容, 然后把size数组的值置为1即可
/*** 本题主要就是涉及到并查集的打标签的技巧, 还有如何拆散一个并查集* 首先就是关于并查集打标签: 其实就是给集团领袖节点打上标签信息(类似size数组)* 关于拆散并查集: 其实就是把father数组重新设置为自身, size置为1(如果有的话)*/class Solution {// 并查集轻量化的板子private static final int MAXN 100001;private static final int[] father new int[MAXN];private static final boolean[] knowSecrets new boolean[MAXN];private static int find(int i){if(i ! father[i]){father[i] find(father[i]);}return father[i];}private static boolean isSameSet(int a, int b){return find(a) find(b);}private static void union(int a, int b){if(!isSameSet(a, b)){father[find(a)] find(b);}}// 初始化并查集private static void build(int n, int firstPerson){for(int i 0; i n; i){father[i] i;knowSecrets[i] false;}// 初始化知道秘密的集团(只需要给领袖节点打上标签就好了)union(0, firstPerson);knowSecrets[0] true;knowSecrets[firstPerson] true;}public ListInteger findAllPeople(int n, int[][] meetings, int firstPerson) {// 首先初始化并查集build(n, firstPerson);// 把meetings进行排序便于处理Arrays.sort(meetings, (a, b) - a[2] - b[2]);int l 0;int r 0;while(l meetings.length){// 首先把r指针置为l的位置r l;int tempL l;// 向右侧扩充(结束的时候r指向的下一个不同的元素的边界位置)while(r meetings.length meetings[r][2] meetings[l][2]){r;}// 先便利一边并查集进行集合元素的合并while(l r){union(meetings[l][0], meetings[l][1]);if(isSameSet(0, meetings[l][0])) knowSecrets[meetings[l][0]] true;if(isSameSet(0, meetings[l][1])) knowSecrets[meetings[l][1]] true;l;}// 再次便利一边这个时间点的元素进行集合的拆解l tempL;while(l r){if(!isSameSet(meetings[l][0], 0) !isSameSet(meetings[l][1], 0)){father[meetings[l][0]] meetings[l][0];father[meetings[l][1]] meetings[l][1];}l;}l r;}// 进行元素的收集ListInteger res new ArrayList();for(int i 0; i n; i){if(isSameSet(0, i)){res.add(i);}}return res;}
}建图及其拓扑排序篇
建图的方法有三种, 邻接表, 邻接矩阵, 以及链式前向星, 我们更推荐的是静态空间的链式前向星的建图法, 下面是链式前向星的板子
链式前向星建图板子
/*** 关于大厂笔试以及比赛中的建图方式的测试, 其实就是使用静态的数组空间进行建图* 我们设置 3 / 4 / 5 个静态数组空间* head数组(存储点对应的头边编号), next数组(边对应下一条边的编号), to数组(边去往的点), weight数组(边对应的权值), indegree数组(点对应的入度)* 关于拓扑排序(topoSort), 我们最常用的方法其实就是零入度删除法(使用队列, 必要的时候使用小根堆), 关于是否环化的判断我们使用计数器实现* 下面是我们提供的链式建图的板子, 以及拓扑排序的板子*/public class createGraphByLinkedProStar{// 设置点的最大数量private static final int MAXN 10001;// 设置边的最大数量private static final int MAXM 10001;// head数组private static final int[] head new int[MAXN];// next数组private static final int[] next new int[MAXM];// to数组private static final int[] to new int[MAXM];// weight数组private static final int[] weight new int[MAXM];// indegree数组(统计入度)private static final int[] indegree new int[MAXN];// cnt统计边的数量private static int cnt 1;// 添加边的方法(顺便统计入度)private static void addEdge(int u, int v, int w){next[cnt] head[u];to[cnt] v;weight[cnt] w;head[u] cnt;indegree[v];}// 初始化静态空间(只需要清空head以及indegree数组)然后建图(这里是有向带权图)private static void build(int n, int[][] edges){cnt 1;for(int i 0; i n; i){indegree[i] 0;head[i] 0;}for(int[] edge : edges){addEdge(edge[0], edge[1], edge[2]);}}// 拓扑排序(topoSort的板子)private static int[] topoSort(int n){// 首先创建一个队列(将来可以作为结果返回)int[] queue new int[n];int l 0;int r 0;// 遍历入度表, 添加所有0入度的点进队列for(int i 0; i n; i){if(indegree[i] 0){queue[r] i;}}// 利用链式前向星的遍历开始跑拓扑排序int elemCnt 0;while(l r){int cur queue[l];elemCnt;for(int ei head[cur]; ei ! 0; ei next[ei]){if(--indegree[to[ei]] 0){queue[r] to[ei];}}}return elemCnt n ? queue : new int[0];}}课程表
标准的使用拓扑排序的板子 加上链式前向星建图法直接打败 100 % class Solution {// 设置点的最大数量private static final int MAXN 10001;// 设置边的最大数量private static final int MAXM 10001;// head数组private static final int[] head new int[MAXN];// next数组private static final int[] next new int[MAXM];// to数组private static final int[] to new int[MAXM];// indegree数组(统计入度)private static final int[] indegree new int[MAXN];// cnt统计边的数量private static int cnt 1;// 添加边的方法(顺便统计入度)private static void addEdge(int u, int v){next[cnt] head[u];to[cnt] v;head[u] cnt;indegree[v];}// 初始化静态空间(只需要清空head以及indegree数组)然后建图(这里是有向带权图)private static void build(int n, int[][] edges){cnt 1;for(int i 0; i n; i){indegree[i] 0;head[i] 0;}for(int[] edge : edges){addEdge(edge[1], edge[0]);}}// 拓扑排序(topoSort的板子)private static int[] topoSort(int n){// 首先创建一个队列(将来可以作为结果返回)int[] queue new int[n];int l 0;int r 0;// 遍历入度表, 添加所有0入度的点进队列for(int i 0; i n; i){if(indegree[i] 0){queue[r] i;}}// 利用链式前向星的遍历开始跑拓扑排序int elemCnt 0;while(l r){int cur queue[l];elemCnt;for(int ei head[cur]; ei ! 0; ei next[ei]){if(--indegree[to[ei]] 0){queue[r] to[ei];}}}return elemCnt n ? queue : new int[0];}public int[] findOrder(int numCourses, int[][] prerequisites) {build(numCourses, prerequisites);return topoSort(numCourses);}
}
