算法竞赛常用数据结构（JAVA版）（尽可能使用数组来模拟）
里面的截图取自acwing算法基础课程截图方便理解
在一般的算法竞赛中一般常用数组来模拟数据结构可以比调库更加节省运行时间不容易被卡时间
链表
本次讲的是用数组来模拟链表：
一个数组来记录值一个数组来记录链表的下一个节点的下标具体信息如下
案例：
package ACWing.DataStructure;
//826. 单链表
//本题的注意点k要减一
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/27 16:47
*/
public class Link {
static int idx=0;
static int[]e=new int[100010];
static int[]ne=new int[100010];//记录着下一个节点的下标
static int h;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
h=-1;
int m=sc.nextInt();
sc.nextLine();
while (m-->0){
String s=sc.next();
if("I".equals(s)){
int k=sc.nextInt();
int x=sc.nextInt();
add(k-1,x);
}
if("H".equals(s)){
int x=sc.nextInt();
add_head(x);
}
if("D".equals(s)){
int k=sc.nextInt();
if(k==0){
h=ne[h];
}else {
delect(k-1);
}
}
}
for (int i = h; i != -1; i=ne[i]) {
System.out.print(e[i]+" ");
}
}
public static void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];//保存k原本的指向
ne[k]=idx++;//改变k的指向
}
public static void add_head(int x){//头插法
e[idx]=x;
ne[idx]=h;
h=idx++;
}
public static void delect(int k){
ne[k]=ne[ne[k]];
//直接跳过本下一个节点变可实现删除
}
}
而双链表也与上方一致用一个l和r数组来代表本节点的左右俩边的数组下标
案例：
package ACWing.DataStructure;
//
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/27 21:35
*/
public class DoubleLinkedList {
static int[]e=new int[100010];
static int[]r=new int[100010];
static int[]l=new int[100010];
static int idx=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
sc.nextLine();
r[0] = 1;l[1] = 0;
idx = 2;
while (m-->0){
String s=sc.next();
if("L".equals(s)){
int x=sc.nextInt();
add(0,x);
}
if("R".equals(s)){
int x=sc.nextInt();
add(l[1],x);
}
if("D".equals(s)){
int x=sc.nextInt();
remove(x+1);
}
if("IL".equals(s)){
int k=sc.nextInt();
int x=sc.nextInt();
add(l[k+1],x);
}
if("IR".equals(s)){
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]+" ");
}
}
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){
l[r[k]]=l[k];
r[l[k]]=r[k];
}
}
单链表一般在图论中用来形成邻接表可以实现对图的快速建模
栈
栈特征：先进后出
package ACWing.DataStructure;
//828. 模拟栈
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/28 15:20
*/
public class AnalogStack {
static int[]stk=new int[100010];
static int tt;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
sc.nextLine();
while (m-->0){
String s=sc.next();
if("push".equals(s)){
int x=sc.nextInt();
push(x);
}
if("pop".equals(s)){
if(!empty()){
pop();
}
}
if("empty".equals(s)){
if(empty()){
System.out.println("YES");
}else {
System.out.println("NO");
}
}
if("query".equals(s)){
if(!empty()){
System.out.println(query());
}
}
}
}
public static void push(int x){
stk[++tt]=x;
}
public static void pop(){
tt--;
}
public static boolean empty(){
if(tt>0){
return false;
}else {
return true;
}
}
public static int query(){
return stk[tt];
}
}
队列
特征：先进先出（在bfs使用较多）
package ACWing.DataStructure.队列;
//829. 模拟队列
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/28 16:39
*/
public class AnalogQueue {
static int[]q=new int[100010];
static int tt=-1;//尾
static int hh;//头
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
sc.nextLine();
while (m-->0){
String s=sc.next();
if("push".equals(s)){
int x=sc.nextInt();
push(x);
}
if("pop".equals(s)){
if(!empty()){
pop();
}
}
if("empty".equals(s)){
if(empty()){
System.out.println("YES");
}else {
System.out.println("NO");
}
}
if("query".equals(s)){
if(!empty()){
System.out.println(query());
}
}
}
}
public static void push(int x){
q[++tt]=x;
}
public static void pop(){
hh++;
}
public static boolean empty(){
if(hh<=tt){
return false;
}
return true;
}
public static int query(){
int n=q[hh];
return n;
}
}
单调栈
不断去优化栈中的元素
因为新输入的x下标一定比已入栈的元素的下标大又因为x的值更小比x大的数的范围更大所以可以将栈中比x大的元素弹出将x入栈作为比较基准
例子：如果a<b,b<c那么a<c必定成立而且a 的下标大距离更近
模板：
package ACWing.DataStructure.单调栈;
//830. 单调栈
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/28 17:09
*/
public class MonotonicStack {
static int[]stk=new int[100010];
static int tt;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
while (m-->0){
int x=sc.nextInt();
while (tt!=0&&stk[tt]>=x)tt--;//找出比x小的数并把比x大的数弹出如果因为如果a<b,b<c那么a<c必定成立而且x的下标更加大
if(tt>0){
System.out.print(stk[tt]+" ");
}else {
System.out.print("-1 ");
}
stk[++tt]=x;
}
}
}
单调队列
将比a【i】大的数删掉用下标数大而且值小的数的下标作为队头以此类推每次便可以看到最小数在队头
模板：
package ACWing.DataStructure.单调队列;
//154. 滑动窗口
import java.io.*;
/**
* @author :chenjie
* @date :Created 2022/12/28 17:44
*/
public class SlidingWindow {
static int[]q=new int[1000010];
static int[]a=new int[1000010];
static int hh,tt;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
String[] st = bf.readLine().split(" ");
int m = Integer.parseInt(st[0]);
int k = Integer.parseInt(st[1]);
String[] str = bf.readLine().split(" ");
for(int i = 0 ; i < m ; i ++ ) a[i] = Integer.parseInt(str[i]);
hh=0;
tt=-1;
for (int i = 0; i < m; i++) {
if(hh<=tt&&i-k+1>q[hh]){//个数超过k个了维持窗口数量
hh++;
}
while (hh<=tt&&a[q[tt]]>=a[i]){//将比a【i】大的数删掉用下标数大而且值小的数的下标作为队头以此类推每次便可以看到最小数在队头
tt--;
}
q[++tt]=i;
if(i>=k-1){
System.out.print(a[q[hh]]+" ");
}
}
System.out.println();
hh=0;
tt=-1;
for (int i = 0; i < m; i++) {
if(hh<=tt&&i-k+1>q[hh]){//个数超过k个了
hh++;
}
while (hh<=tt&&a[q[tt]]<=a[i]){
tt--;
}
q[++tt]=i;
if(i>=k-1){
System.out.print(a[q[hh]]+" ");
}
}
}
}
KMP
感觉用处不大暂时省略
Trie
模板/案例
package ACWing.DataStructure.trie树;
//835. Trie字符串统计
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/28 21:31
*/
public class TrieStringStatistics {
static int[][]son=new int[100010][26];//可以看成存储的节点第一行第二行这样的
static int[]cnt=new int[100100];
static int idx;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
sc.nextLine();
for (int i = 0; i < n; i++) {
String s=sc.next();
String x=sc.next();
char[] str = x.toCharArray();
if("I".equals(s)){
insert(str);
}
if("Q".equals(s)){
System.out.println(query(str));
}
}
}
public static void insert(char[] str){
int p=0;
for (int i = 0;i<str.length; i++) {
int u=str[i]-'a';
if(son[p][u]==0){
son[p][u]=++idx;
}
p=son[p][u];
}
cnt[p]++;//以p这个下标对应的节点结尾的个数
}
public static int query(char[] str){
int p=0;
for (int i = 0; i < str.length; i++) {
int u=str[i]-'a';
if(son[p][u]==0){
return 0;
}
p=son[p][u];
}
return cnt[p];
}
}
并查集
优化：路径压缩
指的是在遍历寻找父节点的过程中将遍历过的点的父节点全部改为根节点这样便可以实现O（1）级别的查询了
模板/精髓:
public static int find(int x){//理解为查找祖宗节点+路径压缩
if (p[x]!=x){
p[x]=find(p[x]);
}
return p[x];
}
堆
原理如下所示n/2的层为倒二层所以遍历之后各个父节点都会比子节点来的小以此类推h【1】必定是最小的可能（切记这里并不是全部排序只能保证最小的值在根节点，同层中的大小未进行排序所以最后的h数组不一定是从小到大的）
for (int i = n/2; i !=0; i--) {//精髓
down(i);
}
模板：
public static void down(int u){//将最小值赋值到父节点向下遍历
int t=u;
if(u*2+1<=size&&h[u*2+1]<h[t]){
t=u*2+1;
}
if(u*2<=size&&h[u*2]<h[t]){
t=u*2;
}
if(t!=u){
int temp=h[u];
h[u]=h[t];
h[t]=temp;
down(t);
}
}
public static void up(int u){//向上遍历与上类似不过只判断父节点与我的大小符合就换位
while (u/2>0&&h[u/2]>h[u]){
int temp=h[u];
h[u]=h[u/2];
h[u/2]=temp;
down(u/2);
u=u/2;
}
}
升级优化堆：
因为在堆排序中下标在不断的变化所以想要知道他这个点是第几次插入的需要引入以下俩种映射关系
static int[]hp=new int[100010];//存储的是这个元素在ph中对应的下标 static int[]ph=new int[100010];//存储的是第i次输入的这个值在h中存在的下标
例子：
ph[m]=size; hp[size]=m; h[size]=x;
m表示第几次插入的位数
而hp和h应用着相同的下标这样便可以通过hp知道h中的数是第几次插入的
不然在排序过程中ph不会随着对应h的值的下标变化而变化了
模板：
public static void down(int u){
int t=u;
if(u*2<=size&&h[u*2]<h[t]){
t=u*2;
}
if(u*2+1<=size&&h[u*2+1]<h[t]){
t=u*2+1;
}
if(u!=t){
swap(u,t);
down(t);
}
}
public static void up(int u){
while (u/2>0&&h[u/2]>h[u]){
swap(u,u/2);
u=u/2;
}
}
public static void swap(int a,int b){
int temp=ph[hp[a]];
ph[hp[a]]=ph[hp[b]];
ph[hp[b]]=temp;
temp=hp[a];
hp[a]=hp[b];
hp[b]=temp;
temp=h[a];
h[a]=h[b];
h[b]=temp;
}
HashMap
拉链法
类似邻接表
操作方法：链式前向星
模板：
public static void insert(int x){
int k=(x%100003+100003)%100003;//保持永远是正数的情况
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
public static boolean find(int x){
int k=(x%100003+100003)%100003;
for (int i = h[k]; i !=-1; i=ne[i]) {
if(e[i]==x){
return true;
}
}
return false;
}
开放寻址法
如果本位置有人就向后遍历查询直到找到空位
模板省略：就是遍历。。。
字符串哈希
经验值：p与q的值可以形成一个几乎没有冲突的哈希表
个人理解：
这个算法就是将字符串转化为一个无冲突的整形及数字，通过p进制的运算可以求出字符串字串的对应数字如果相等则表示着俩个字符子串相等，思想上一点类似前缀和不过是通过一个公式实现这些字符串的存储和快速查找
求l到r这一段的公式：
h[r]-h[l-1]*p[r-l+1]
思想便是移位 ，例子：123456-12*10000=3456
便可求出l到r中间的字符串对应的数字
生成公式：
h[i]=h[i-1]*P+str[i]-'a'+1;//加一的原因是如果a对应0的话那aa也是0无法区分所以必须从1开始
p[i]=p[i-1]*P;
模板：
package ACWing.DataStructure.哈希表;
//841. 字符串哈希
import java.util.Arrays;
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/30 13:10
*/
public class StringHash {
static Long[]h=new Long[100010];
static Long[]p=new Long[100010];
static int base=131;
//模板求一段的哈希值
public static long get(int l,int 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();
sc.nextLine();
String s=sc.next();
char[] str = s.toCharArray();
//生成哈希表
p[0]= Long.valueOf(1);
h[0]= Long.valueOf(0);
for (int i = 1; i <= n; i++) {
h[i]=h[i-1]*base+str[i-1]-'a'+1;
p[i]=p[i-1]*base;
}
//案例比较
while (m-->0){
int l1=sc.nextInt();
int r1=sc.nextInt();
int l2=sc.nextInt();
int r2=sc.nextInt();
if(get(l1,r1)==get(l2,r2)){
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
}