目录
一、数组模拟单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +?指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
单链表是我们很常见的一种线性表 适用于经常增删元素的场景 在我们日常使用中我们可以采用结构体的方式来实现链表 也就是把很多个 Node 串在一起 ，但是这种结构体的实现是很慢的 因为java中new一个对象所耗费的时间是很多的 ，因此我们采用数组模拟就能很好的规避。同时，数组模拟也有其缺陷---浪费一定的数组空间 但这并不在我们算法的考虑范围之内
思路：首先定义一个e【】数组用来存储元素本来的值，用一个ne【】数组来存储下一个结点next的下标 idx用于存储元素的下标
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第?kk?个插入的数后面的数；
- 在第?kk?个插入的数后插入一个数。
现在要对该链表进行?MM?次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第?kk?个插入的数并不是指当前链表的第?kk?个数。例如操作过程中一共插入了?nn?个数，则按照插入的时间顺序，这?nn?个数依次为：第?11?个插入的数，第?22?个插入的数，…第?nn?个插入的数。
输入格式
第一行包含整数?MM，表示操作次数。
接下来?MM?行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数?xx。D k，表示删除第?kk?个插入的数后面的数（当?kk?为?00?时，表示删除头结点）。I k x，表示在第?kk?个插入的数后面插入一个数?xx（此操作中?kk?均大于?00）。输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤1000001≤M≤100000
所有操作保证合法。
import java.util.*;
public class Main{
static int N = 100010;
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0,head = -1;
public static void add_head(int x) {
e[idx] = x; //先在e中把x存下来
ne[idx] = head; //因为是头插，所以该元素的next必须是head
head = idx++; //此时真正的头节点已经是idx了 并且idx++ 用于下一次的插入元素
}
public static void add(int k, int x) { // 此函数用于在下标为k 的点后插入值为x的元素
e[idx] = x; // 老样子，先把x存起来
ne[idx] = ne[k]; //新的next应该是原来k的next
ne[k] = idx++; //k的next就是idx 并把idx++
}
public static void remove(int k) { //删除k下标之后的元素
ne[k] = ne[ne[k]]; //让k直接指向next的next
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
while (m -- > 0) {
String s = sc.next();
if (s.equals("H")) {
int x = sc.nextInt();
add_head(x);
} else if (s.equals("D")) {
int k = sc.nextInt();
if (k == 0) head = ne[head];
else remove(k - 1);
} else {
int k = sc.nextInt();
int x = sc.nextInt();
add(k - 1,x);
}
}
for (int i = head; i != -1;i = ne[i]) {
System.out.print(e[i] + " ");
}
}
}二、数组模拟双链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
事实上，双链表相比单链表就多了一个指向前一个元素的指针，仅此而已。
在实现双链表时，我们采用一种简化的方式，使用 l【】数组表示向前的指针 r【】数组表示向后的指针 同时 r【0】指向双链表起始位置? l[1] 指向双链表结束位置
实现一个双链表，双链表初始为空，支持?55?种操作：
- 在最左侧插入一个数；
- 在最右侧插入一个数；
- 将第?kk?个插入的数删除；
- 在第?kk?个插入的数左侧插入一个数；
- 在第?kk?个插入的数右侧插入一个数
现在要对该链表进行?MM?次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第?kk?个插入的数并不是指当前链表的第?kk?个数。例如操作过程中一共插入了?nn?个数，则按照插入的时间顺序，这?nn?个数依次为：第?11?个插入的数，第?22?个插入的数，…第?nn?个插入的数。
输入格式
第一行包含整数?MM，表示操作次数。
接下来?MM?行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数?xx。R x，表示在链表的最右端插入数?xx。D k，表示将第?kk?个插入的数删除。IL k x，表示在第?kk?个插入的数左侧插入一个数。IR k x，表示在第?kk?个插入的数右侧插入一个数。输出格式
共一行，将整个链表从左到右输出。
import java.util.*;
public class Main{
static int N = 100010;
static int idx;
static int[] e = new int[N];
static int[] l = new int[N];
static int[] r = new int[N];
public static void init() {
r[0] = 1;
l[1] = 0;
idx = 2;
}
public static void add(int k, int x) {
e[idx] = x; //先把元素存下来在考虑指针关系
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx++;
}
public static void remove(int k) { //这里是删除下标为k的元素
l[r[k]] = l[k];
r[l[k]] = r[k];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
init();
int m = sc.nextInt();
while (m -- > 0) {
String s = sc.next();
if (s.equals("L")) { //最左端插入x
int x = sc.nextInt();
add(0,x);
} else if (s.equals("R")) {
int x = sc.nextInt();
add(l[1],x);
} else if (s.equals("D")) { // 删除第k个元素 但我们数组中已经存了两个边界值 0 和 1 所以是 k - 1 + 2
int k = sc.nextInt();
remove(k + 1);
} else if (s.equals("IL")) {
int k = sc.nextInt();
int x = sc.nextInt();
add(l[k + 1],x);
} else {
int k = sc.nextInt();
int x = sc.nextInt();
add(k + 1,x);
}
}
for (int i = r[0]; i != 1; i = r[i]) {
System.out.print(e[i] + " ");
}
}
}三、数组模拟栈
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
总的来说，栈要满足先进后出的特点
实现一个栈，栈初始为空，支持四种操作：
push x?– 向栈顶插入一个数?xx；pop?– 从栈顶弹出一个数；empty?– 判断栈是否为空；query?– 查询栈顶元素。现在要对栈进行?MM?个操作，其中的每个操作?33?和操作?44?都要输出相应的结果。
输入格式
第一行包含整数?MM，表示操作次数。
接下来?MM?行，每行包含一个操作命令，操作命令为?
push x，pop，empty，query?中的一种。输出格式
对于每个?
empty?和?query?操作都要输出一个查询结果，每个结果占一行。其中，
empty?操作的查询结果为?YES?或?NO，query?操作的查询结果为一个整数，表示栈顶元素的值。数据范围
1≤M≤1000001≤M≤100000,
1≤x≤1091≤x≤109
所有操作保证合法。输入样例：
10 push 5 query push 6 pop query pop empty push 4 query empty输出样例：
5 5 YES 4 NO
import java.util.*;
public class Main{
static int N = 100010;
static int tt = -1;
static int[] stk = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
while (m -- > 0) {
String s = sc.next();
if (s.equals("push")) {
int x = sc.nextInt();
stk[++tt] = x;
} else if (s.equals("pop")) {
tt--;
} else if (s.equals("empty")) {
if (tt == -1) System.out.println("YES");
else System.out.println("NO");
} else {
System.out.println(stk[tt] );
}
}
}
}栈的的代码实现非常简单，仅需要维持一个尾结点即可?
1、表达式求值
给定一个表达式，其中运算符仅包含?
+,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。注意：
- 数据保证给定的表达式合法。
- 题目保证符号?
-?只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2)?之类表达式均不会出现。- 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过?231?1231?1。
- 题目中的整除是指向?00?取整，也就是说对于大于?00?的结果向下取整，例如?5/3=15/3=1，对于小于?00?的结果向上取整，例如?5/(1?4)=?15/(1?4)=?1。
- C++和Java中的整除默认是向零取整；Python中的整除
//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过?105105。
输入样例：
(2+2)*(1+1)输出样例：
8
分析这道题：请问在何时我们需要从栈中弹出一个操作符，两个数字进行计算呢？答案是：
当当前字符的优先级低于前一个字符时，如: 1 * 2 + 3 当我们计算到+时，我们需要对之前的数进行操作。因此栈中的操作符优先级一定是从低到高的，因为如果出现从高到低这个‘高’就会被我们处理。所以我们因次可以分出两种情况： 1、无括号，就碰到由高优先级到低优先级，正常的操作即可? 2、 有括号，从后往前计算，保证了优先级从高到低（因为栈中由低到高） 最后我们处理完栈中所有操作符即可
import java.util.*;
public class Main{
public static void eval(Deque<Character> op,Deque<Integer> num) {
char c = op.pop();
int b = num.pop(); //取出一个操作符，两个数进行运算
int a = num.pop();
if (c == '+') {
num.push(a + b);
} else if (c == '-') {
num.push(a - b);
} else if (c == '*') {
num.push(a * b);
} else {
num.push(a / b);
}
}
public static void main(String[] args) {
HashMap<Character,Integer> map = new HashMap(); //建立map，并存入优先级
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
Deque<Character> op = new LinkedList(); //准备两个栈，存操作符，存元素
Deque<Integer> num = new LinkedList();
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
for(int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
if (Character.isDigit(c)) { //如果是数字我们可能涉及拼接
int sum = 0;
int j = i;
while(j < s.length() && Character.isDigit(s.charAt(j))) {
sum = sum * 10 + s.charAt(j) - '0';
j++;
}
i = j - 1;//由于是for循环，所以i要跳到j的前一个位置
num.push(sum);
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.peek() != '(') {
eval(op,num);
}
op.pop(); //把左括号弹出去
} else {
while (!op.isEmpty() && op .peek() != '(' && map.get(c) <= map.get(op.peek()) ) {
eval(op,num);
}
op.push(c);
}
}
while(!op.isEmpty()) {
eval(op,num);
}
System.out.print(num.pop());
}
}四、数组模拟队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
同样，一句话总结队列就是先进先出 ，因此我们要维持头和尾两个指针
实现一个队列，队列初始为空，支持四种操作：
push x?– 向队尾插入一个数?xx；pop?– 从队头弹出一个数；empty?– 判断队列是否为空；query?– 查询队头元素。现在要对队列进行?MM?个操作，其中的每个操作?33?和操作?44?都要输出相应的结果。
输入格式
第一行包含整数?MM，表示操作次数。
接下来?MM?行，每行包含一个操作命令，操作命令为?
push x，pop，empty，query?中的一种。输出格式
对于每个?
empty?和?query?操作都要输出一个查询结果，每个结果占一行。其中，
empty?操作的查询结果为?YES?或?NO，query?操作的查询结果为一个整数，表示队头元素的值。数据范围
1≤M≤1000001≤M≤100000,
1≤x≤1091≤x≤109,
所有操作保证合法。输入样例：
10 push 6 empty query pop empty push 3 push 4 pop query push 6输出样例：
NO 6 YES 4
import java.util.*;
public class Main{
static int tt = -1,hh = 0;
static int q[] = new int[100010];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
while (m -- > 0) {
String s = sc.next();
if (s.equals("push")) {
int x = sc.nextInt();
q[++tt] = x;
} else if (s.equals("pop")) {
hh++;
} else if (s.equals("empty")) {
if (hh <= tt) System.out.println("NO");
else System.out.println("YES");
} else {
System.out.println(q[hh]);
}
}
}
}五、单调栈
单调栈顾名思义里边存储的元素是单调的，一般来说就分为单调递增栈和单调递减栈。
给定一个长度为?NN?的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出??1?1。
输入格式
第一行包含整数?NN，表示数列长度。
第二行包含?NN?个整数，表示整数数列。
输出格式
共一行，包含?NN?个整数，其中第?ii?个数表示第?ii?个数的左边第一个比它小的数，如果不存在则输出??1?1。
数据范围
1≤N≤1051≤N≤105
1≤数列中元素≤1091≤数列中元素≤109输入样例：
5 3 4 2 7 5输出样例：
-1 3 -1 2 2
分析这道题，要我们寻找元素左侧比他小的第一个数，试想，假如我们当前元素比上一个元素小，那是不是说明上一个元素永远没有成为这个“左边第一个比他小的数”?。因此我们队列就没有存储上一个元素的必要了，因此，总的来说，栈里的元素总体上就是单调上升的
import java.util.*;
public class Main{
static int tt = -1;
static int[] stk = new int[100010];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i ++) {
int num = sc.nextInt();
while (tt != -1 && stk[tt] >= num) {
tt--; //弹出这个数
}
if (tt == -1) System.out.print(-1+" ");
else System.out.print(stk[tt]+" ");
stk[++tt] = num;
}
}
}六、单调队列
单调队列又叫滑动窗口 同样的遇到这类问题我们在队列中存储的元素也是单调的
比如下面这道题：
给定一个大小为?n≤106n≤106?的数组。
有一个大小为?kk?的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到?kk?个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为?
[1 3 -1 -3 5 3 6 7]，kk?为?33。
窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数?nn?和?kk，分别代表数组长度和滑动窗口的长度。
第二行有?nn?个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3 1 3 -1 -3 5 3 6 7输出样例：
-1 -3 -3 -3 3 3 3 3 5 5 6 7
首先说明一点，java中打印行为是一个非常耗时的操作，所以这道题如果我们用普通的System.out.print打印就会超时。因此我们需要采用快输，也就是PrintWtiter类 打印完成后记得flush即可
分析这道题：如果我们遍历到当前数比前一个数小，并且他的位置还靠后，那么是不是说明我的滑动窗口?中前一个数不可能作为答案出现，因为窗口是向后滑动的，因此前一个数我们可以从队列中剔除，如果当前队列的头在滑动窗口中，我们就打印它，否则，我们把头往后移一位，再打印（因为我们的窗口每次只往后移动一位）
注意：由于要判断头还在不在窗口中，因此我们队列中存的是下标。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
int n = sc.nextInt();
int k = sc.nextInt();
int tt = -1,hh = 0;
int[] q = new int[1000010];
int[] a = new int[1000010];
for (int i = 0; i < n; i ++) {
a[i] = sc.nextInt();
}
for(int i = 0; i < n; i++) {
if(hh <= tt && q[hh] < i-k+1) hh++;
while(hh <= tt && a[i] <= a[q[tt]]) tt--;
q[++tt] = i;
if(i >= k-1) pw.print(a[q[hh]]+" ");
}
pw.println();
tt = -1;
hh = 0;
for (int i = 0; i < n; i ++) {
if(hh <= tt && q[hh] < i-k+1) hh++;
while(hh <= tt && a[i] >= a[q[tt]]) tt--;
q[++tt] = i;
if (i >= k - 1) pw.print(a[q[hh]] + " ");
}
pw.flush();
}
}七、KMP
kmp是在主串中查找子串的一种匹配算法，本质上是双指针，相比传统的N^2暴力匹配，kmp利用了匹配失败包含的有效信息，总的时间复杂度是O（N）
给定一个模式串?SS，以及一个模板串?PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串?PP?在模式串?SS?中多次作为子串出现。
求出模板串?PP?在模式串?SS?中所有出现的位置的起始下标。
输入格式
第一行输入整数?NN，表示字符串?PP?的长度。
第二行输入字符串?PP。
第三行输入整数?MM，表示字符串?SS?的长度。
第四行输入字符串?SS。
输出格式
共一行，输出所有出现位置的起始下标（下标从?00?开始计数），整数之间用空格隔开。
数据范围
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106输入样例：
3 aba 5 ababa输出样例：
0 2
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String p = sc.next();
int m = sc.nextInt();
String s = sc.next();
int[] next = getNext(p);
int p1 = 0;
int p2 = 0;
while (p1 < s.length() && p2 < p.length()) {
if (s.charAt(p1) == p.charAt(p2)) {
p1++;
p2++;
} else if (p2 != 0) {
p2 = next[p2];
} else {
p1 ++;
}
}
if (p2 == p.length()) System.out.print(p1 - p2);
else System.out.print(-1);
}
public static int[] getNext(String s) { //我们规定next的第一个元素一定是-1
if (s.length() == 1) return new int[] {-1};
int[] next = new int[s.length()];
next[0] = -1; //第一个元素一定是-1，因为它前面没有元素
next[1] = 0; //第二个元素一定是0，因为虽然它前边有一个元素，但最长前后缀不能包括子串本身
int i = 2;
int cn = 0; //cn 初始化时是 i - 1
while (i < s.length()) {
if (s.charAt(i - 1) == s.charAt(cn)) {
next[i++] = ++cn;
} else if (cn != 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
}八、Trie?
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
维护一个字符串集合，支持两种操作：
I x?向集合中插入一个字符串?xx；Q x?询问一个字符串在集合中出现了多少次。共有?NN?个操作，输入的字符串总长度不超过?105105，字符串仅包含小写英文字母。
输入格式
第一行包含整数?NN，表示操作数。
接下来?NN?行，每行包含一个操作指令，指令为?
I x?或?Q x?中的一种。输出格式
对于每个询问指令?
Q x，都要输出一个整数作为结果，表示?xx?在集合中出现的次数。每个结果占一行。
数据范围
1≤N≤2?104
对于字典树，我们要明确它的子节点分支，例如这道题，题目中说明了只会出现小写英文字母，因此它的子节点分支就是26。我们就需要一个二维数 song【N】【26】 N 应该是所有结点的总数量。idx用于给每个结点编号，还需要一个cnt【】数组用于记录以当前下标结尾的字符串一共出现了多少次。
import java.util.*;
public class Main{
static int N = 100010;
static int idx;
static int[][] song = new int[N][26];
static int[] cnt = new int[N];
public static void insert(String s) {
int p = 0;
for (int i = 0; i < s.length(); i ++) {
int u = s.charAt(i) - 'a';
if (song[p][u] == 0) {
song[p][u] = ++idx;
}
p = song[p][u];
}
cnt[p]++;
}
public static int query(String s) {
int p = 0;
for (int i = 0; i < s.length(); i ++) {
int u = s.charAt(i) - 'a';
if (song[p][u] == 0) return 0;
p = song[p][u];
}
return cnt[p];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n -- > 0) {
String s1 = sc.next();
if (s1.equals("I")) {
String s2 = sc.next();
insert(s2);
} else {
String s2 = sc.next();
System.out.println(query(s2));
}
}
}
}1.最大异或对
在给定的?NN?个整数?A1，A2……ANA1，A2……AN?中选出两个进行?xorxor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数?NN。
第二行输入?NN?个整数?A1A1～ANAN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231输入样例：
3 1 2 3输出样例：
3?
思路：我们知道，相同的两个数异或之后是1，异或根据二进制位的不同来异或，不同为1，相同为0，因此我们采用这样一种思路：二进制从高到低，我们每次都?尽量选取不同的位，那么最后得到的就一定是最小的异或对，这个查找只要实现N次，我们就可以找到最大的异或对。这个实现，就采用Trie来实现
import java.util.*;
public class Main{
static int N = 3000010; //为什么N开这么大，因为我们是以位数构建线段树的，因此输入范围是 10^5 * 31
static int[][] song = new int[N][2];
static int idx = 0;
public static void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i --) {
int u = x >> i & 1;
if (song[p][u] == 0) song[p][u] = ++idx;
p = song[p][u];
}
}
public static int query(int x) {
int p = 0;
int res = 0;
for(int i = 30; i >= 0; i --) {
int s = x >> i & 1;
if (song[p][1-s] != 0) {
res+= 1 << i;
p = song[p][1-s];
} else {
//res+= 0 << i;
p = song[p][s];
}
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] e = new int[n + 10];
for (int i = 0; i < n; i ++) {
e[i] = sc.nextInt();
insert(e[i]);
}
int max = 0;
for (int i = 0; i < n; i ++) {
max = Math.max(max,query(e[i]));
}
System.out.print(max);
}
}九、并查集
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集顾名思义，核心操作就两个，1：合并两个集合? ? ? ? 2：查询两个元素是不是在同一个集合中
一共有?nn?个数，编号是?1～n1～n，最开始每个数各自在一个集合中。
现在要进行?mm?个操作，操作共有两种：
M a b，将编号为?aa?和?bb?的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为?aa?和?bb?的两个数是否在同一个集合中；输入格式
第一行输入整数?nn?和?mm。
接下来?mm?行，每行包含一个操作指令，指令为?
M a b?或?Q a b?中的一种。输出格式
对于每个询问指令?
Q a b，都要输出一个结果，如果?aa?和?bb?在同一集合内，则输出?Yes，否则输出?No。每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4输出样例：
Yes No Yes
难度：简单 时/空限制：1s / 64MB 总通过数：41099 总尝试数：66005 来源：模板题,AcWing 算法标签
思路：对于并查集，我们的合并和查找其实都是建立在find函数上实现的，同时我们要在函数中要实现路径压缩 ，确保这个并查集子和父之间的距离不会太长。
import java.util.*;
public class Main{
static int N = 100010;
static int p[] = new int[N];
public static int find(int x) { //让每个结点都指向根节点，实现路径压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //最开始有 1 ~ n 个数
for (int i = 1; i <= n; i ++) {
p[i] = i; //初始化集合，让每个元素单独成为一个集合
}
int m = sc.nextInt();
while (m -- > 0) {
String s = sc.next();
int a = sc.nextInt();
int b = sc.nextInt();
if (s.equals("M")) { //合并两个集合，只需要让其中一个的父节点指向另一个父节点
p[find(a)] = find(b);
} else {
if (find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}1.连通块中点的数量
给定一个包含?nn?个点（编号为?1～n1～n）的无向图，初始时图中没有边。
现在要进行?mm?个操作，操作共有三种：
C a b，在点?aa?和点?bb?之间连一条边，aa?和?bb?可能相等；Q1 a b，询问点?aa?和点?bb?是否在同一个连通块中，aa?和?bb?可能相等；Q2 a，询问点?aa?所在连通块中点的数量；输入格式
第一行输入整数?nn?和?mm。
接下来?mm?行，每行包含一个操作指令，指令为?
C a b，Q1 a b?或?Q2 a?中的一种。输出格式
对于每个询问指令?
Q1 a b，如果?aa?和?bb?在同一个连通块中，则输出?Yes，否则输出?No。对于每个询问指令?
Q2 a，输出一个整数表示点?aa?所在连通块中点的数量每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5输出样例：
Yes 2 3
?思路：这道题本质上就是并查集加了一个维持区间个数的变形，我们只需要再创建一个数组用于维持集合的个数即可。
import java.util.*;
public class Main{
static int N = 100010;
static int[] p = new int[N];
static int[] size = new int[N];
public static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
p[i] = i;
size[i] = 1;
}
while (m -- > 0) {
String s = sc.next();
if (s.equals("C")) {
int a = sc.nextInt();
int b = sc.nextInt();
if (find(a) == find(b)) continue;
else {
size[find(b)] += size[find(a)]; //size操作一定要在更改父节点之前完成，
p[find(a)] = find(b);
}
} else if (s.equals("Q1")) {
int a = sc.nextInt();
int b = sc.nextInt();
if (find(a) == find(b)) System.out.println("Yes");
else System.out.println("No");
} else {
int a = sc.nextInt();
System.out.println(size[find(a)]);
}
}
}
}2、食物链
动物王国中有三类动物?A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。
AA?吃?BB，BB?吃?CC，CC?吃?AA。
现有?NN?个动物，以?1～N1～N?编号。
每个动物都是?A,B,CA,B,C?中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这?NN?个动物所构成的食物链关系进行描述：
第一种说法是?
1 X Y，表示?XX?和?YY?是同类。第二种说法是?
2 X Y，表示?XX?吃?YY。此人对?NN?个动物，用上述两种说法，一句接一句地说出?KK?句话，这?KK?句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中?XX?或?YY?比?NN?大，就是假话；
- 当前的话表示?XX?吃?XX，就是假话。
你的任务是根据给定的?NN?和?KK?句话，输出假话的总数。
输入格式
第一行是两个整数?NN?和?KK，以一个空格分隔。
以下?KK?行每行是三个正整数?D，X，YD，X，Y，两数之间用一个空格隔开，其中?DD?表示说法的种类。
若?D=1D=1，则表示?XX?和?YY?是同类。
若?D=2D=2，则表示?XX?吃?YY。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤500001≤N≤50000,
0≤K≤1000000≤K≤100000输入样例：
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5输出样例：
3
难度：中等 时/空限制：1s / 64MB 总通过数：24472 总尝试数：52856 来源：《算法竞赛进阶指南》, 模板题 , NOI2001 , POJ1182 , kuangbin专题 算法标签
挑战模式
食物链这道题，不容易觉察他是一道并查集的题，但如果仔细分析我们会发现：“说法”的格式只有两种，a和b同类，a吃b。因此我们可以知道在编号不同的个体中，永远都是真的，因为你无法确定他们之间的关系。只有凭借“说法”，把他们联系在一个集合中，才有可能辨别真假，在一个集合中，我们采用d【】数组来记录一种关系：任何集合中的一个点，d为1表示吃根节点，d为2表示被根结点吃，d为0表示和根节点是同类。因此，我们可以在说法中联立“集合”来辨别真假。
import java.util.*;
public class Main{
static int N = 50010;
static int[] p = new int[N];
static int[] d = new int[N]; //d的定义是子节点和父节点之间的距离
public static int find(int x) { //由于进行路径压缩的时候改变了d，因此要更新d
if (p[x] != x) {
int pa = p[x];
p[x] = find(p[x]);
d[x] += d[pa];
}
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 1; i <= n; i ++) {
p[i] = i;
}
int res = 0;
while (k -- > 0) {
int op = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if (a > n || b > n ) {
res++;
continue;
}
int pa = find(a);
int pb = find(b);
if (op == 1) { //a 和 b 是同类
if (pa == pb && (d[a] - d[b]) % 3 != 0 ) res++; //不在一个集合肯定是真的，只需要统计在一个集合的情况
else if (pa != pb) { //把a和b 合并
p[pa] = pb;
d[pa] = d[b] - d[a]; //d是子节点和父节点的距离
}
} else {
if (pa == pb && (d[a] - d[b] - 1) % 3 != 0) res++;
else if (pa != pb) {
p[pa] = pb;
d[pa] = d[b] - d[a] + 1;
}
}
}
System.out.print(res);
}
}十、哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
我们通常使用的哈希表往往有两种实现方式，一种是拉链法，另一种是开放寻址法（蹲坑法）
哈希表的实现往往要一个高效的哈希函数，这个函数能让所有的元素均匀的分布在表中，并尽量降低哈希冲突，如何应对哈希冲突就造成了两种不同的实现方式，拉链法采用的是链表，冲突了就在后边开条链表接着，开放寻址法就跳过当前位置，寻找一个空着的位置。
维护一个集合，支持如下几种操作：
I x，插入一个数?xx；Q x，询问数?xx?是否在集合中出现过；现在要进行?NN?次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数?NN，表示操作数量。
接下来?NN?行，每行包含一个操作指令，操作指令为?
I x，Q x?中的一种。输出格式
对于每个询问指令?
Q x，输出一个询问结果，如果?xx?在集合中出现过，则输出?Yes，否则输出?No。每个结果占一行。
数据范围
1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109输入样例：
5 I 1 I 2 I 3 Q 2 Q 5输出样例：
Yes No
首先来看拉链法：?
import java.util.*;
public class Main{
static int N = 100010; //采用拉链法实现，因此需要静态链表
static int idx = 0;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
public static void add(int x) {
int k = (x % N + N) % N; //获取x % N 之后的下标，因为x有可能是负数，因此%完之后 + N 再 % N
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++; //经典的头插代码
}
public static boolean find(int x) {
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) { //我们的idx从0 开始，因此-1 是一个特殊值，初始化链表的时候默认为-1
if (e[i] == x) return true;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < N; i ++) { //一定要记得初始话，否则find找不到-1 死循环！
h[i] = -1;
}
while (n -- > 0) {
String s = sc.next();
int x = sc.nextInt();
if (s.equals("I")) add(x);
else {
if (find(x)) System.out.println("Yes");
else System.out.println("No");
}
}
}
}开放寻址法：
import java.util.*;
public class Main{
static int N = 200003;
static int nulls = 0x3f3f3f3f;
static int[] h = new int[N];
public static int find(int x) {
int k = (x % N + N) % N;
while (h[k] != nulls && h[k] != x) {
k ++;
if (k == N) k = 0;
}
return k;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < N; i ++) {
h[i] = nulls;
}
while (n -- > 0) {
String s = sc.next();
int x = sc.nextInt();
int k = find(x);
if (s.equals("I")) {
h[k] = x;
} else {
if (h[k] == nulls) System.out.println("No");
else System.out.println("Yes");
}
}
}
}1、字符串哈希
?哈希：哈希可以理解为一种映射关系（或者可以理解为一种函数关系），在数字哈希里面是数字到数字的映射，在字符串哈希里是字符串到数字的映射，这种巧妙的映射关系保证了哈希算法在处理某些问题时具有高效性。
在字符串哈希为字符串到数字的映射关系。
我们假设一种映射关系为字符串到P进制的数的映射关系（P是任意的），那么就有了如何映射的问题：
在映射完成后要保证能完成一系列的字符串查找，比较，删除等操作，所以必须保证这种映射关系是一一映射的，不能有冲突（这也是字符串哈希和数字哈希的一大区别，对于数字哈希我们有专门的处理冲突的手段，因为应用范围的不一样，所以字符串哈希我们不会处理冲突），为了让冲突的最小化，所以我们这里取P = 131 or 13331，并且将字符串映射到2 64 2^{64}264范围内的数字在这时的冲突几率非常小。
总结：?p = 131 or 13331, 在2 64 2^{64}264范围内的数字映射字符串前缀哈希：?要想处理出来字符串任意区间内的hash， 我们首先要处理出来所有的前缀hash，例如：
ABCDE我们先处理出来h[1]代表A的hash，h[2]代表B的·······以此类推，处理办法：进制的求算公式：
例如十进制的数字：145：P = 10.
1 ? 1 0 2 + 4 ? 10 + 5 ? 1 0 0 1*10^2+4*10+5*10^01?102+4?10+5?100?总结公式为下列：
a × P 4 + b × P 3 + c × P 2 + d × P 1 + e × P 0 a×P ^4+b×P ^3+c×P ^2+d×P ^1+e×P ^0a×P4+b×P3+c×P2+d×P1+e×P0
要处理某一个前缀的hash值，要把字符串当成一个P进制的数，然后每一位的字母的ASCII值就代表这一位的数字，则abcde的hash值为上述式子
import java.util.*;
public class Main{
static int P = 131; //131 默认不出现哈希冲突
static int N = 100010;
static long[] p = new long[N]; //采用long类型是因为存在指数爆炸，long自动取模2 ^ 64
static long[] h = new long[N];
public static long find(int l, int r) { //返回 l 到 r 的哈希值
return h[r] - h[l - 1] * p[r - l + 1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
String s = sc.next();
p[0] = 1;// p 的 0 次方是 1
for (int i = 1; i <= n ; i ++) {
p[i] = p[i - 1] * P ;
h[i] = h[i - 1] * P + s.charAt(i - 1);
}
while ( m -- > 0) {
int l1 = sc.nextInt();
int r1 = sc.nextInt();
int l2 = sc.nextInt();
int r2 = sc.nextInt();
if (find(l1,r1) == find(l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}十一、堆
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
关于堆操作的实现细节及原理，我都在之前一篇博客总结过了，这里仅给出实现代码
https://blog.csdn.net/qq_59539549/article/details/123259521?spm=1001.2014.3001.5502输入一个长度为?nn?的整数数列，从小到大输出前?mm?小的数。
输入格式
第一行包含整数?nn?和?mm。
第二行包含?nn?个整数，表示整数数列。
输出格式
共一行，包含?mm?个整数，表示整数数列中前?mm?小的数。
数据范围
1≤m≤n≤1051≤m≤n≤105，
1≤数列中元素≤1091≤数列中元素≤109输入样例：
5 3 4 5 1 3 2输出样例：
1 2 3
堆排序，首先我们要建堆，因此需要向下调整的操作（事实上也可以向上调整，但经过证明向下调整建堆的时间复杂度是O（N）?，而向上调整建堆的时间复杂度毫无疑问是O（N * log N）
每一次我们从堆中选一个最大的数，交换到最后，并且缩小堆的size,一直重复，知道所有的数都被选出，堆排序完成，毫无疑问时间复杂度O（N * log N)
import java.util.*;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int size;
public static void swap(int i,int j) {
int t = h[i];
h[i] = h[j];
h[j] = t;
}
public static void down(int i) {
int left = 2 * i + 1;
while (left < size) {
int less = left + 1 < size && h[left] > h[left + 1] ? left + 1 : left;
less = h[less] < h[i] ? less : i;
if (less == i) break;
swap(i,less);
i = less;
left = 2 * i + 1;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 0; i < n; i ++){
h[i] = sc.nextInt();
size++;
}
for (int i = (size -2) / 2; i >= 0; i --) {
down(i);
}
while (m -- > 0) {
System.out.print(h[0] + " ");
h[0] = h[--size];
down(0);
}
}
}1、模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数?xx；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第?kk?个插入的数；C k x，修改第?kk?个插入的数，将其变为?xx；现在要进行?NN?次操作，对于所有第?22?个操作，输出当前集合的最小值。
输入格式
第一行包含整数?NN。
接下来?NN?行，每行包含一个操作指令，操作指令为?
I x，PM，DM，D k?或?C k x?中的一种。输出格式
对于每个输出指令?
PM，输出一个结果，表示当前集合中的最小值。每个结果占一行。
数据范围
1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109
数据保证合法。输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM输出样例：
-10 6
?思路：比起普通的堆，我们多了第k个元素的这种映射，因此我们需要一个数组ph记录从第几个到堆的映射，hp从堆到第几个的映射。
import java.util.*;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int[] ph = new int[N];
static int[] hp = new int[N];
static int size,m;
public static void swap(int[] arr,int i,int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void heap_swap(int i, int j) {
swap(ph,hp[i],hp[j]);
swap(hp,i,j);
swap(h,i,j);
}
public static void up(int i) {
int pa = (i - 1) / 2;
while (h[i] < h[pa]) {
heap_swap(pa,i);
i = pa;
pa = (i - 1) / 2;
}
}
public static void down(int i) {
int left = 2 * i + 1;
while (left < size) {
int less = (left + 1 < size && h[left+1] < h[left]) ? left + 1 : left;
less = h[less] < h[i] ? less : i;
if (less == i) return;
heap_swap(i,less);
i = less;
left = 2 * i + 1;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n -- > 0) {
String s = sc.next();
if(s.equals("I")) {
int x = sc.nextInt();
ph[m] = size;
hp[size] = m;
h[size] = x;
up(size);
size++;
m++;
} else if (s.equals("PM")) {
System.out.println(h[0]);
} else if (s.equals("DM")) {
heap_swap(0,-- size);
down(0);
} else if (s.equals("D")) {
int k = sc.nextInt();
k = ph[k-1];
heap_swap(k,size-1);
size--;
up(k);
down(k);
} else {
int k = sc.nextInt();
int x = sc.nextInt();
k = ph[k - 1];
h[k] = x;
up(k);
down(k);
}
}
}
}
