当前位置：首页 > java >正文

ACWing 算法基础课-数据结构笔记

java 2025/8/14 6:12:54

这里写目录标题

单链表
- 例题
单调栈
单调队列
- 应用
- 举例——滑动窗口
Tried
- 最大异或值
并查集
- 食物链
堆
- 堆的基本结构
- 具体实现
- 堆的操作包括：
- 模拟堆
- 堆排序
哈希表
- 代码
- 字符串哈希

单链表

ne存储的下标

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{head = -1;idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove()
{head = ne[head];
}
//将下标是k的点后面的点个删掉
void remove(int k){ne[k] = ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}

例题

注意点：下标；第k个的理解

// 实现一个单链表，链表初始为空，支持三种操作：// 向链表头插入一个数；
// 删除第 k 个插入的数后面的数；
// 在第 k 个插入的数后插入一个数。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 100010;
int e[N],ne[N],idx,head;
void init(){head = -1;idx = 0;
}
void insert(int k,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}
void insert(int x){e[idx] = x;ne[idx] = head;head = idx++;
}void remove(int k){ne[k] = ne[ne[k]];
}
int main()
{string op;int m,x,k;cin >> m;init();while (m -- ){cin >> op;if(op == "H"){cin >> x;insert(x);}else if(op == "D"){cin >> k;if(k == 0){head = ne[head];}else{remove(k-1);}}else if(op == "I"){cin >> k >> x;insert(k-1,x);}}for(int i=head;i!=-1;i=ne[i]){cout << e[i] <<" ";}
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

算法关键点：如果右边的数比左边的小，那左边的那些数没有存在的意义;
维护栈：
如果该数小于栈中数，栈顶的数一直弹出，因为比该数小的数都没有意义；
如果该数大于栈中数，入栈听候发落（栈中数还有意义）；
找最小的数：栈顶小于该数，即为结果；大于该数，一直出栈（出栈道数比当前值大且在更左边，所以没有任何意义了），直到有数比该数小，或者栈空；
如此相当于维护了一个单调递增栈

#include<iostream>
#include<stack>
using namespace std;
const int N = 1e5+10;
int a[N];
int n;
int main()
{cin >> n;for(int i=0;i<n;i++){cin >> a[i];}//左边第一个小的数，stack<int> stk;/*算法关键点：如果右边的数比左边的小，那左边的那些数没有存在的意义;维护栈：如果该数小于栈中数，栈顶的数一直弹出，因为比该数小的数都没有意义；如果该数大于栈中数，入栈听候发落（栈中数还有意义）；找最小的数：栈顶小于该数，即为结果；大于该数，一直出栈，直到有数比该数小，或者栈空如此相当于维护了一个单调递增栈*/for(int i=0;i<n;i++){while(!stk.empty()){if(stk.top() >= a[i]) stk.pop();else break;}if(stk.empty()) cout << "-1" <<" ";else cout << stk.top() << " ";stk.push(a[i]);}
}

单调队列

队列元素成单调性
动机：输出最大值最小值时间复杂度为O(1)

应用

大概就两种情况：

求滑动窗口的极值
找离他最近的最小的或者最大的元素

举例——滑动窗口

在这里插入图片描述

为了可以同时弹出队首和队尾的元素，我们需要使用双端队列
https://www.acwing.com/solution/content/97229/
**- 主要思想：**求窗口最小值时,如果入队元素a小于队尾元素b，则队尾元素存在无意义（因为a在b一定在，而b又比a小），所以不断删去比入队元素大的队尾元素，以此为维持队列单调递增性。

如果滑动窗口中的数，比刚入队时的数大且在前面，这个数毫无意义了
队列中存储的是数组的下标！所以可以通过下标方便的判断是否在滑动窗口中
求最大值同理

note

队尾元素（最先入队的）是答案，其特点为：下标最早，如果它不是最小，早就排除了
- 所以最小值是维护单调递增
- 最大值是维护单调递减
如何确保队列的元素是最近K个？
- 通过下标判断
- 判断队首元素是否是窗口左边的第一个元素 (维护单调队列时，将等于的元素也入队，这样就算有重复的元素，也能这样判断。因为每次仅弹出一个，那队列还会剩下另一个）
代码链接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;
const int N = 1e5+10;
int a[N];
int n,k;int main()
{/* 求最小值时：如果滑动窗口中的数，比刚入队时的数大且在前面，这个数毫无意义了如果队列中的数比要入队的数大，则弹出维护一个单调队列——队头到队尾，递减：*求窗口最小值时,如果入队元素a小于队尾元素b，则队尾元素存在无意义
（因为a在b一定在，而b又比a小），
所以不断删去比入队元素大的队尾元素，以此为维持队列单调递增性。*/cin >> n >> k;for(int i=0;i<n;i++) cin >> a[i];deque<int> q;for(int i=0;i<n;i++){while(!q.empty() && q.back() >= a[i]){q.pop_back();}// 不断从队首弹出元素，直到队首元素在窗口中为止 // 两种方案：存入下标，判断下标；判断队首元素是否是窗口左边的第一个元素if(i - k >= 0 && q.front() == a[i-k]) q.pop_front(); q.push_back(a[i]);//窗口形成再输入值if(i >= k-1) cout << q.front() << " ";//单调递增,所以输出队尾}}

#include<iostream>
#include<deque>
using namespace std;
const int N = 1e6+10;
int a[N];int n,k;
// int q[N],head=0,tt=-1;// bool isempty(){
//     return head == tt;
// }deque<int> q;int main(){cin >> n >> k;for(int i=0;i<n;i++){cin >> a[i];}// //队列存储的是下表// for(int i=0;i<n;i++){  //     //最小值，左边比新入队大的，毫无意义；所以，从小到大，大的是新入队队//     while(head >= tt && a[q[tt]] > a[i]){//         tt--;//     }//     q[++tt] = i;//     if(i - k == q[head]) head++;//     if(i >= k - 1){//         cout << q[head] << " ";//     }// }for(int i=0;i<n;i++)//队列存储元素{while(!q.empty() && q.back() > a[i]){q.pop_back();}q.push_back(a[i]);if(q.front() == a[i-k]) q.pop_front();if(i >= k - 1) cout << q.front() << " ";}q.clear();cout << endl;for(int i=0;i<n;i++){while(!q.empty() && a[q.back()] < a[i]){q.pop_back();}q.push_back(i);if(i-k == q.front()) q.pop_front();if(i >= k-1) cout << a[q.front()] << " ";}}

Tried

基本作用：tried树是一个高效的存储和查找字符串集合的数据结构。
存储方式：以字典树的方式存储
在这里插入图片描述

如上图，右边的输存储了左边的字符串。所有单词结尾的地方做一个标记，这样就高效的查找和存储某个单词

适用场景：字母的个数不是很多，要么全是小写字母，要么全是大写字母
字典树

注意：和哈夫曼树没得关系，只是像

代码实现：

0号点既是根节点，又是空节点
son[][]存储树中每个节点的子节点；列数为26的原因，仅包含26个小写字母，可以通过son[p][str
cnt[]存储以每个节点结尾的单词数量
idx当前用到的下标，idx为0时既是空节点，也是根节点

int son[N][26], cnt[N], idx;
// 插入一个字符串
void insert(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++ idx;p = son[p][u];//令p为下一个节点}cnt[p] ++ ;
}// 查询字符串出现的次数
int query(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

在这里插入图片描述

最大异或值

基本思路：将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异
时间复杂度O(nlogn)
在这里插入图片描述
x>>k & 1表示x的二进制中x的第k位是0还是1

并查集

应用场景
并查集可以以近乎O(1)快速支持这两个操作：

将两个集合合并
询问两个元素是否在一个集合中:

基本原理：每个集合用一棵树表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

基本操作：
问题1：如何判断树根：if(p[x] == x)
问题2：如何求x的集合编号：while(p[x] != x) x = p[x] 即只要不是树根，一直往上走
问题3：如何合并两个结合：px是x集合编号，py是y的集合编号。p[x] = y（直接把x插入到y）

优化：
路径压缩：第一遍遍历时把所有节点指向根节点，O(logn)
按秩合并：优化不明显，从来不写O(logn)
在这里插入图片描述
代码模板：

 int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b);

注意：

不要忘记并查集的初始化操作

进阶：
使用并查集时常常需要绑定一些额外的信息，常见的有以下两种：
第二种可以用每个点到根节点的距离来表示分类关系，如食物链的题

其他
如果要记录并查集的集合数目，每次合并时将总的集合数目减一即可，可参考：岛屿数量

基本的代码模板code

#include<iostream>using namespace std;const int N=100010;
int p[N];//定义多个集合
//返回x的祖宗节点+路径压缩
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);/*经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:p[x]=x;*/return p[x];//找到了便返回祖宗节点的值
}int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=i;while(m--){char op[2];int a,b;scanf("%s%d%d",op,&a,&b);if(*op=='M') p[find(a)]=find(b);//集合合并操作else //判断两个节点是否在同一个集合里面{if(find(a)==find(b))//如果祖宗节点一样,就输出yesprintf("Yes\n");elseprintf("No\n");}}return 0;
}

食物链

一遍是需要在并查集上维护额外信息，比如在联通块题目中需要维护节点数量

基本思想：用节点到根节点的距离信息来表示与根节点的关系，
在这里插入图片描述
具体做法：每个节点存储到父节点的距离，然后做路径压缩即得到到根节点的距离。

两节点x和y之间的关系通过两节点到根节点的聚类来判断，如下图：y吃根节点，x被根节点吃，所以x吃y

堆

堆的基本结构

堆是一个完全二叉树
stl的堆就是优先队列
堆的存储：使用数组存储，x的左儿子2x，x的右儿子2x+1

下标从1开始，因为从0开始，2x这些不好计算

具体实现

用下面两个基础操作维护五个基本操作：
下沉：down(k）第k个数变大后往下调
上浮：up(k)，第k个数变小后往上浮

堆的操作包括：

建堆
插入一个数：heap[++size]=x,up(size)
求集合中的最小值:heap[1]
删除最小值：把最后一个元素覆盖堆顶元素
heap[1]=heap[size];size--;down(1)

(删除最后一个点，把最后一个点挪到前面来，这样很方便）
删除任意一个元素：删除第k点，heap[k] = heap[size];size–;down(k)；up(k)

down(k)和up(k)只执行一个
修改任意一个元素:heap[k]=x;down(k),up(k)

前三个是最基本的操作

模拟堆

关键点：需要知道插入的第k个数的位置

h[N]:堆
ph[k]:存储第k个插入的数的在堆中的下标的值
hp[k]:建立堆元素到ph的链接

原因:在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的k下标对应idx（第idx个插入），所以需要hp数组方便查找idx。

在这里插入图片描述

#include<iostream>
#include<algorithm>
using namespace std;const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v)
{   swap(h[u],h[v]); swap(hp[u],hp[v]);     swap(ph[hp[u]],ph[hp[v]]);            }void down(int u)
{int t=u;if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;if(u!=t){heap_swap(u,t);down(t);}
}
void up(int u)
{if(u/2>0&&h[u]<h[u/2]) {heap_swap(u,u/2);up(u>>1);}
}int main()
{int n;cin>>n;int m=0;      //m用来记录插入的数的个数//注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少//对应上文 m即是hp中应该存的值while(n--){string op;int k,x;cin>>op;if(op=="I"){cin>>x;m++;h[++cur_size]=x;ph[m]=cur_size;hp[cur_size]=m;//down(size);up(cur_size);}else if(op=="PM")    cout<<h[1]<<endl;else if(op=="DM"){heap_swap(1,cur_size);cur_size--;down(1);}else if(op=="D"){cin>>k;int u=ph[k];                //这里一定要用u=ph[k]保存第k个插入点的下标heap_swap(u,cur_size);          //因为在此处heap_swap操作后ph[k]的值已经发生 cur_size--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误up(u);down(u);}else if(op=="C"){cin>>k>>x;h[ph[k]]=x;                 //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以down(ph[k]);                //所以可直接传入ph[k]作为参数up(ph[k]);}}return 0;
}

堆排序

建堆O（n）;

#include<iostream> 
#include<algorithm>using namespace std;const int N = 100010;int h[N], mySize;int n, m;void down(int u)
{int t = u;if (2 * u <= mySize && h[t] > h[2 * u])t = 2 * u;if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])t = 2 * u + 1;if (u != t){swap(h[u], h[t]);//得到三个节点里最小的那个值down(t);}
}int main()
{cin >> n >> m;mySize = n;for (int i = 1; i <= n; i++)scanf("%d", &h[i]);for (int i = n / 2; i; i--)down(i);while (m--){cout << h[1] << " ";h[1] = h[mySize--];down(1);}return 0;
}

哈希表

哈希表时间复杂度都为O(1)
在这里插入图片描述

哈希表的作用：大的区域映射到小区域
哈希函数一般就是取模，如x mod 11，模一般去质数，这样取冲突的概率最小；比如10万左右要模十万零三
两种处理冲突的方式
1. 拉链法：
2. 开放寻址法
算法题中对哈希表一般只有添加和查找两种操作，无删除
执行删除也是逻辑删除，即将相应值添加标记，表示已经删除了
初始化开设的一维数组一般为实际大小的两到三倍，如果是1e5，一般开个2e5;

代码

1.拉链法

#include<iostream>
#include<cstring>using namespace std;
const int N = 100003; // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度
int h[N],e[N],ne[N],idx;int n,x;
void insert(int x){// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int t = (x%N+N)%N;e[idx] = x;ne[idx] = h[t];h[t] = idx;idx++;
}
bool find(int x){int t = (x % N + N) % N;for(int i = h[t];i!=-1;i=ne[i]){if(x == e[i]){return true;}}return false;
}
int main(){cin >> n;memset(h,-1,sizeof h);while(n--){char op[2];scanf("%s%d",op,&x);if(!strcmp(op,"I")){insert(x);}else{if(find(x)){puts("Yes");}else{puts("No");}}}}