域名服务商是什么意思_达州seo排名_搜索网站大全_可以入侵的网站

蓝桥杯刷题 Day3 队列、并查集

---

---

前言

今天写牛客网模板题中的队列、并查集

---

一、队列

原题地址: 队列

import java.util.*;public class Main {public static void main(String[] args) {// 输入Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.nextLine(); // 消耗换行符// 定义队列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {// 输入整行String line = scanner.nextLine();String[] prats = line.split(" ");// 处理switch (prats[0]){case "push":int x = Integer.parseInt(prats[1]);queue.add(x);break;case "pop":if(queue.isEmpty()) {System.out.println("error");} else {System.out.println(queue.poll());}break;case "front":if(queue.isEmpty()) {System.out.println("error");} else {System.out.println(queue.peek());}break;}}}}

1. 解题思路

调用Queue接口的add()、poll()、peek()方法，难点在于处理输入

2. 拆解代码

2.1 输入n

// 输入Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.nextLine(); // 消耗换行符// 定义队列Queue<Integer> queue = new LinkedList<>();

2.2 处理输入的字符串

for (int i = 0; i < n; i++) {// 输入整行，用一个空格分隔开字符串和数字，存储在prats数组中String line = scanner.nextLine();String[] prats = line.split(" ");// 处理switch (prats[0]){case "push":int x = Integer.parseInt(prats[1]);queue.add(x);break;case "pop":if(queue.isEmpty()) {System.out.println("error");} else {System.out.println(queue.poll());}break;case "front":if(queue.isEmpty()) {System.out.println("error");} else {System.out.println(queue.peek());}break;}}

二、并查集

原题地址: 并查集

import java.util.*;public class Main {private static final int N = (int) 1e5 + 5; // 预分配空间private static int[] parent  =new int[N]; // 存储父节点private static int[] size = new int[N]; // 存储每个集合的大小private static int[] rank = new int[N]; // 按秩合并优化（树的高度）public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();//1. 初始化并查集initialize(n);// 处理输入的m组关系，合并集合for (int i = 0; i < m; i++) {int u = scanner.nextInt();int v = scanner.nextInt();union(u, v);}// 统计结果：班级数和最大班级人数int classCount = 0, maxSize = 0;for (int i = 1; i <= n; i++) {if(parent[i] == i){ // 合并后，非根节点的父节点会指向其他人，只有根节点的父节点始终是自己classCount++;maxSize = Math.max(maxSize, size[i]);}}System.out.println(classCount + " " +maxSize);}// 初始化函数private static void initialize(int n){for (int i = 1; i <= n; i++) {parent[i] = i; // 初始父节点指向自己size[i] = 1; // 每个集合初始大小为1rank[i] = 1; // 初始树高度为1}}// 查找根节点（路径压缩优化）x——>y——>z,parent[x]=y;private  static int find(int x){if(parent[x] != x){parent[x] = find(parent[x]);}return parent[x];}// 合并集合private static void union(int x, int y){int rootX = find(x);int rootY = find(y);if(rootY != rootX){if(rank[x] > rank[y]){// 将矮树合并到高树中，并增加树高parent[rootY] = rootX;size[rootX] += size[rootY];}else {parent[rootX] = rootY;size[rootY] += size[rootX];if(rank[rootY] == rank[rootX]){rank[rootY]++;}}}}
}

1. 解题思路

1.1 问题抽象

将两个不同集合合并成一个集合，用到树的概念，将多条“树”合并成一条树，矮树并高树，数值增加。

1.2 解题步骤

1. 初始化并查集
2. 查找对应要求的集合
3. 合并
4. 输出

2. 拆解代码

2.1 数据结构的定义

private static final int N = (int) 1e5 + 5; // 预分配空间private static int[] parent  =new int[N]; // 存储父节点private static int[] size = new int[N]; // 存储每个集合的大小private static int[] rank = new int[N]; // 按秩合并优化（树的高度）

2.2 主函数

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();//1. 初始化并查集initialize(n);// 处理输入的m组关系，合并集合for (int i = 0; i < m; i++) {int u = scanner.nextInt();int v = scanner.nextInt();union(u, v);}// 统计结果：班级数和最大班级人数int classCount = 0, maxSize = 0;for (int i = 1; i <= n; i++) {if(parent[i] == i){ // 合并后，非根节点的父节点会指向其他人，只有根节点的父节点始终是自己classCount++;maxSize = Math.max(maxSize, size[i]);}}System.out.println(classCount + " " +maxSize);}

2.3 初始化函数

 private static void initialize(int n){for (int i = 1; i <= n; i++) {parent[i] = i; // 初始父节点指向自己size[i] = 1; // 每个集合初始大小为1rank[i] = 1; // 初始树高度为1}}

2.4 查找根节点（路径压缩，递归调用）

// 查找根节点（路径压缩优化）x——>y——>z,parent[x]=y;private  static int find(int x){if(parent[x] != x){parent[x] = find(parent[x]);}return parent[x];}

2.5 合并集合

private static void union(int x, int y){int rootX = find(x);int rootY = find(y);if(rootY != rootX){if(rank[x] > rank[y]){// 将矮树合并到高树中，并增加树高parent[rootY] = rootX;size[rootX] += size[rootY];}else {parent[rootX] = rootY;size[rootY] += size[rootX];if(rank[rootY] == rank[rootX]){rank[rootY]++;}}}

3. 题后收获

3.1 知识点

1. split( )：自定义分隔符
2. Math.max(a,b)：判断ab的大小

3.2 新菜式

1. 整行输入字符串和数字，用数组隔开：
   String line = scanner.nextLine();
   String[] prats = line.split(" ");
2. final预分配空间：private static final int N = (int) 1e5 + 5;
3. 递归指针