单链表
- 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~n
for (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))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("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万左右要模十万零三
两种处理冲突的方式
拉链法：
开放寻址法
算法题中对哈希表一般只有添加和查找两种操作，无删除
执行删除也是逻辑删除，即将相应值添加标记，表示已经删除了
初始化开设的一维数组一般为实际大小的两到三倍，如果是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");
}
}
}
}
字符串哈希
处理字符串的利器，很多字符串难题可以用字符串哈希来简单处理，非常牛逼的算法
基本原理：将字符串使用P进制通过进制转换映射到十进制数，所以就可以用一个数来表示一个字符串。然后这个数可能会很大，所以需要对Q取模
- 不能映射成0，不然A,AA都是0了，冲突了
- 字符串哈希是假设不存在冲突， 一般来说P = 131或13331 ，Q = 2的64次方，是不存在冲突的