算法.图论-习题全集(Updating)
本节设置的意义重要就是为了复习图论算法, 实行从标题剖析的角度,更深入的明白图论算法…
并查集篇
并查集简介以及常见技巧
并查集是一种用于大团体查找, 合并等操纵的数据结构, 常见的方法有
[*]find: 用来查找元素在大团体中的代表元素(这里使用的是扁平化的处置处罚)
[*]isSameSet: 用来查找两个元素是不是一个大团体的(其实就是find的应用)
[*]union: 用来合并两大团体的元素
关于并查集打标签的技巧, 其实我们之前的size数组也是一种打标签的逻辑, 其实打标签就是给每一个团体的代表节点打上标签即可, 另有我们在并查集的标题中通常会设置一个sets作为集合的总数量(每次合并–), 这是一个常见的技巧, 并查集的细节我们在这里不进行过多的介绍, 在之前的章节中有过细的描述…
并查集板子(洛谷)
这里我们的并查集的板子使用的是洛谷的板子(小挂大的优化都没必要其实)
// 并查集模版(洛谷)
// 本实现用递归函数实现路径压缩，而且省掉了小挂大的优化，一般情况下可以省略
// 测试链接 : https://www.luogu.com.cn/problem/P3367
import 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;
public static int n;
public static void build() {
for (int i = 0; i <= n; i++) {
father = i;
}
}
public static int find(int i) {
if (i != father) {
father = find(father);
}
return father;
}
public static boolean isSameSet(int x, int y) {
return find(x) == find(y);
}
public static void union(int x, int y) {
father = 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();
}
}
情侣牵手问题
https://i-blog.csdnimg.cn/direct/6ea8bd7deb724bc993e8fd054f42fb08.png#pic_center
本题的突破点就是假如一个大团体里面有 n 对情侣, 那么我们至少要互换 n - 1次(通过把情侣进行编号)
// 这次我们尝试使用轻量版的并查集来解决这道题
class Solution {
private static final int MAX_CP = 31;
private static final int[] father = new int;
private static int sets = 0;
private static int find(int i) {
if (i != father) {
father = find(father);
}
return father;
}
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 = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n) {
for (int i = 0; i < n; i++) {
father = i;
}
sets = n;
}
public int minSwapsCouples(int[] row) {
build(row.length / 2);
for (int i = 0; i < row.length; i += 2) {
int n1 = row / 2;
int n2 = row / 2;
union(n1, n2);
}
return row.length / 2 - sets;
}
}
相似的字符串组
https://i-blog.csdnimg.cn/direct/f39ae24162ad4c018d9f2127cd69fcd1.png#pic_center
其实就是摆列每一个位置, 然后判定是不是一组的就OK了
// 还是使用一下轻量级的并查集板子
class Solution {
private static final int MAX_SZ = 301;
private static final int[] father = new int;
private static int sets = 0;
private static int find(int i) {
if (i != father) {
father = find(father);
}
return father;
}
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 = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n) {
for (int i = 0; i < n; i++) {
father = i;
}
sets = n;
}
public int numSimilarGroups(String[] strs) {
build(strs.length);
// 主流程的时间复杂度是 O(n ^ 2), 遍历strs的每一个位置
int m = strs.length();
for (int i = 0; i < strs.length; i++) {
for (int j = i + 1; j < strs.length; j++) {
// 获取到两个字符串, 然后计算两个字符串的不同字符数量
String s1 = strs;
String s2 = strs;
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;
}
}
岛屿数量(并查集做法)
https://i-blog.csdnimg.cn/direct/ce97ba405e194f16be3ccbb0667a7a68.png#pic_center
这道题的解法非常多, 比如多源 BFS , 大水添补(其实就是递归加回溯) , 另有今天介绍的并查集的方法(这个方法不是最好的)
// 这个题的并查集做法只要注意一点就可以了: 把一个二维下标转化为一维下标
class Solution {
private static final int MAX_SZ = 301 * 301;
private static final int[] father = new int;
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) {
father = find(father);
}
return father;
}
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 = 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 == '1') {
sets++;
father = getIndex(i, j);
}
}
}
}
public int numIslands(char[][] grid) {
// 初始化并查集并统计 '1' 的数量
build(grid, grid.length, grid.length);
// 遍历grid进行合并
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// 向四个方向扩展
if (grid == '1') {
for (int k = 0; k < 4; k++) {
int nx = i + move;
int ny = j + move;
if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid == '1') {
union(getIndex(i, j), getIndex(nx, ny));
}
}
}
}
}
return sets;
}
// 二维下标转一维下标
private static int getIndex(int i, int j) {
return i * col + j;
}
}
省份数量
https://i-blog.csdnimg.cn/direct/fa5aa5b0edd84eecbf9890dc1e50df2f.png#pic_center
没什么可说的, 就是一个简单的并查集的思路
class Solution {
// 这其实也是一个并查集的题
private static final int MAXM = 201;
private static final int[] father = new int;
private static final int[] size = new int;
private static int sets = 0;
private static int find(int i){
if(i != father){
father = find(father);
}
return father;
}
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 > size){
father = fa;
size += size;
}else{
father = fb;
size += size;
}
sets--;
}
}
private static void build(int n){
for(int i = 0; i < n; i++){
father = i;
size = 1;
}
sets = n;
}
public int findCircleNum(int[][] isConnected) {
// 初始化并查集
build(isConnected.length);
for(int i = 0; i < isConnected.length; i++){
int[] info = isConnected;
for(int j = 0; j < info.length; j++){
if(info == 1){
union(i, j);
}
}
}
return sets;
}
}
移除最多的同行或同列石头
https://i-blog.csdnimg.cn/direct/3510297afaff406f844c3b22e4aa77a6.png#pic_center
其实就是每一个团体末了都会被消成一个元素, 我们中间用哈希表加了一些关于离散化的处置处罚的技巧
// 使用一下轻量版本的并查集加上哈希表进行离散化的操作
class Solution {
private static Map<Integer, Integer> rowFirst = new HashMap<>();
private static Map<Integer, Integer> colFirst = new HashMap<>();
private static final int MAXM = 1001;
private static final int[] father = new int;
private static int sets = 0;
private static int find(int i){
if(i != father){
father = find(father);
}
return father;
}
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 = fb;
sets--;
}
}
// 初始化并查集
private static void build(int n){
for(int i = 0; i < n; i++){
father = 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;
int col = stones;
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;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]