鏈表?
單鏈表
826. 單鏈表 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
int m;
int e[N],ne[N];//記錄數(shù)據(jù)和下一結(jié)點坐標
int head,idx;//當前指向的結(jié)點
void init()
{
head=-1;
idx=0;
}
void addtohead(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
void remove(int x)
{
ne[x]=ne[ne[x]];
}
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
signed main()
{
scanf("%d",&m);
init();
while(m--)
{
char op;
scanf("%s",&op);
if(op=='H')//向鏈表頭插入一個數(shù)x
{
int x;
scanf("%d",&x);
addtohead(x);
}
//第k個插入的數(shù)的對應坐標是k-1
if(op=='D')//刪除第 k個插入的數(shù)后面的數(shù)（當 k為 0時，表示刪除頭結(jié)點）
{
int x;
scanf("%d",&x);
if(!x) head=ne[head];//如果是刪除頭結(jié)點 ，移動頭結(jié)點head
else remove(x-1);
}
if(op=='I')//第 k個插入的數(shù)后面插入一個數(shù) x
{
int k,x;
scanf("%d %d",&k,&x);
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
return 0;
}雙鏈表
827. 雙鏈表 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
int m;
int e[N],l[N],r[N],idx;
void init()
{
r[0]=1,l[1]=0;
idx=2;
}
void add(int k,int x)
{
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx++;
}
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
signed main()
{//0,1代表頭尾
cin>>m;
init();
while(m--)
{
string op;
cin>>op;
if(op=="L")
{
int x;
cin>>x;
add(0,x);
}
if(op=="R")
{
int x;
cin>>x;
add(l[1],x);
}
if(op=="D")
{
int k;
cin>>k;
remove(k+1);
}
if(op=="IL")
{
int k,x;
cin>>k>>x;
add(l[k+1],x);
}
if(op=="IR")
{
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
return 0;
}棧
828. 模擬棧 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
int m;
int stk[N],tt;
void init()
{
tt=0;
memset(stk,0,sizeof(stk));
}
signed main()
{
cin>>m;
init();
while(m--)
{
string op;
cin>>op;
if(op=="push")
{
int x;
cin>>x;
stk[++tt]=x;
}
if(op=="pop")
{
tt--;
}
if(op=="empty")
{
if(tt>0) cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
}
if(op=="query")
{
cout<<stk[tt]<<'\n';
}
}
return 0;
}3302. 表達式求值 - AcWing題庫
遍歷輸入的操作
如果是數(shù)字就存入num的堆棧 （同時注意123，2123這種長數(shù)字要一次性存入）
如果是（? 直接存入op的堆棧
如果是? ）就一直運算，直到遇到（
如果是操作符（如+-*/），一直與棧頂比較運算符優(yōu)先級，如果棧里的運算符優(yōu)先級大就運算，直到目前這個運算符優(yōu)先級小為止。
運算是從num里彈出兩個數(shù)，從op里彈出一個運算符，直接運算。
如果最后遍歷完了，棧內(nèi)還有運算符就算完，最后num棧頂?shù)脑鼐褪亲詈蟮倪\算結(jié)果
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;
stack<char> op;
stack<int> num;
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
void eval()
{
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
int x;
if(c == '+') x = a + b;
else if(c == '-') x = a - b;
else if(c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
string s;
cin >> s;
for(int i = 0; i < s.size(); i++)
{
char c = s[i];
if(isdigit(c))
{
int x = 0, j = i;
while(j < s.size() && isdigit(s[j])) x = 10 * x + s[j++] - '0';
i = j - 1;
num.push(x);
}
else if(c == '(') op.push(c);
else if(c == ')')
{
while(op.size() && op.top() != '(') eval();
op.pop();
}
else
{
while(op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}
隊列
829. 模擬隊列 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
//頭刪尾插
const int N=1e5+10;
int q[N],hh,tt=-1;
int m;
signed main()
{
cin>>m;
while(m--)
{
string op;
cin>>op;
if(op=="push")
{
int x;
cin>>x;
q[++tt]=x;
}else if(op=="pop"){
hh++;
}else if(op=="empty"){
if(hh<=tt) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}else if(op=="query"){
cout<<q[hh]<<endl;
}
}
return 0;
}?單調(diào)棧
830. 單調(diào)棧 - AcWing題庫
?單調(diào)遞增或遞減的棧
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[N],tt;
int n;
signed main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
while(tt&&stk[tt]>=x) tt--;
if(tt) cout<<stk[tt]<<" ";
else cout<<"-1 ";
stk[++tt]=x;
}
return 0;
}單調(diào)隊列
154. 滑動窗口 - AcWing題庫
數(shù)組a存數(shù)值，數(shù)組q模擬隊列。
保持滑動窗口的大小為k。同時保持單調(diào)隊列，也就是如果隊頭的數(shù)比進來的數(shù)大就丟出去，這樣保持隊頭是當前這個區(qū)間內(nèi)的最小值。
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n,k,q[N],a[N];//q[N]存的是數(shù)組下標
int main()
{
int tt=-1,hh=0;//hh隊列頭 tt隊列尾
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(hh<=tt&&i>q[hh]+k-1) hh++;
while(hh<=tt&&a[i]<=a[q[tt]]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
if(hh<=tt&&i>q[hh]+k-1) hh++;
while(hh<=tt&&a[i]>=a[q[tt]]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
return 0;
}?KMP
831. KMP字符串 - AcWing題庫
這篇寫得很好：KMP算法詳解-徹底清楚了(轉(zhuǎn)載+部分原創(chuàng)) - sofu6 - 博客園 (cnblogs.com)??
#include<iostream>
using namespace std;
const int N=100010,M=1000010;
char q[N],s[M];
int ne[N];//保存next數(shù)組
int main()
{
int n,m;
cin>>n>>q+1>>m>>s+1;//下標均從1開始
ne[1]=0;
for(int i=2,j=0;i<=n;i++)
//j表示匹配成功的長度,i表示q數(shù)組中的下標,因為q數(shù)組的下標是從1開始的,只有1個時,一定為0,所以i從2開始
{
while(j&&q[i]!=q[j+1]) j=ne[j];
//如果不行可以換到next數(shù)組
if(q[i]==q[j+1]) j++;
//成功了就加1
ne[i]=j;
//對應其下標
}
//j表示匹配成功的長度,因為剛開始還未開始匹配,所以長度為0
for(int i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=q[j+1]) j=ne[j];
//如果匹配不成功,則換到j對應的next數(shù)組中的值
if(s[i]==q[j+1]) j++;
//匹配成功了,那么j就加1,繼續(xù)后面的匹配
if(j==n)//如果長度等于n了,說明已經(jīng)完全匹配上去了
{
printf("%d ",i-j);
//因為題目中的下標從0開始,所以i-j不用+1;
j=ne[j];
//為了觀察其后續(xù)是否還能跟S數(shù)組后面的數(shù)配對成功
}
}
return 0;
}理解后自己a的版本?
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char p[N],s[N];
int m,n;
int ne[N];
signed main()
{
cin>>n>>p+1>>m>>s+1;
for(int i=2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n)
{
cout<<i-j<<" ";
j=ne[j];
}
}
return 0;
}Trie樹
835. Trie字符串統(tǒng)計 - AcWing題庫
Trie樹：用來高效的存儲和字符串集合的數(shù)據(jù)結(jié)構。?
?
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx; //下標是0的點，既是根節(jié)點，又是空節(jié)點
char str[N];
void insert(char str[])
{
int p=0;
for(int i=0;str[i]!='\0';++i)
{
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
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];
}
signed main()
{
int m;cin>>m;
while(m--)
{
char c;
cin>>c>>str;
if(c=='I') insert(str);
else {
cout<<query(str)<<endl;
}
}
return 0;
}
143. 最大異或?qū)?- AcWing題庫
異或，不進位的加法。
先轉(zhuǎn)化成二進制，進行異或運算后，再轉(zhuǎn)化。
比如3^5=6
3的二進制是011，5的二進制是101
101
011
110（結(jié)果），對應十進制里的6?
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int son[N*31][2];
int idx,n;
void insert(int x)
{
int p=0;
for(int i=31;i>=0;i--)
{
int u=x>>i&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x)
{
int p=0,ret=0;
for(int i=31;i>=0;i--)
{
int u=x>>i&1;
if(son[p][!u])
{
p=son[p][!u];
ret=ret*2+!u;
}else{
p=son[p][u];
ret=ret*2+u;
}
}
return ret^x;
}
signed main()
{
cin>>n;
int maxn=0;
while(n--)
{
int x;
cin>>x;
insert(x);
maxn=max(maxn,query(x));
}
cout<<maxn;
return 0;
}并查集
并查集適于以下操作：
1.合并兩個集合
2.查詢兩個元素是否同一個集合
合并集合?
836. 合并集合 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
int pa=find(a);int pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
}
}
void query(int a,int b)
{
int pa=find(a);
int pb=find(b);
if(pa==pb) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op;
cin>>op;
int a,b;
cin>>a>>b;
if(op=='M') merge(a,b);
if(op=='Q') query(a,b);
}
return 0;
}?連通塊中點的數(shù)量
837. 連通塊中點的數(shù)量 - AcWing題庫
?用集合維護連通塊。
在點之間連邊相當于合并兩個集合。
額外需要注意的操作就只有統(tǒng)計每個集合中的元素個數(shù)，開一個s數(shù)組記錄就好。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N],s[N];//只保證根節(jié)點的size有意義
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)
{
int pa=find(a);int pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
s[pb]+=s[pa];
}
}
void query(int a,int b)
{
int pa=find(a);
int pb=find(b);
if(pa==pb) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i,s[i]=1;
while(m--)
{
char op[5];
cin>>op;
int a,b;
if(op[0]=='C') cin>>a>>b,merge(a,b);
if(op[1]=='1') cin>>a>>b,query(a,b);
if(op[1]=='2') cin>>a,cout<<s[find(a)]<<endl;
}
return 0;
}食物鏈
240. 食物鏈 - AcWing題庫
?有問題可以看這個題解的評論，解答得很漂亮??！
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m;
int p[N],d[N];
int res;
int find(int x)
{
if(p[x]!=x)
{
int t = find(p[x]);//這一步是直接找到根
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
int t,x,y;
cin>>t>>x>>y;
if(x>n||y>n) res++;
else{
int px=find(x),py=find(y);
if(t==1)//同類的
{
if(px==py&&(d[x]-d[y])%3!=0) res++;//如果在一個集合內(nèi)但不滿足同級的條件
else if(px!=py)
{
p[px]=py;
d[px]=d[y]-d[x];
}
}else if(t==2){
if(px==py&&(d[x]-d[y]-1)%3!=0) res++;
else if(px!=py)
{
p[px]=py;
d[px]=d[y]+1-d[x];
}
}
}
}
cout<<res;
return 0;
}堆
堆排序
838. 堆排序 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],r;
void down(int u)
{
int t=u;//標記最小的點
if(2*u<=r&&a[2*u]<a[t]) t=2*u;
if(2*u+1<=r&&a[2*u+1]<a[t]) t=2*u+1;
if(u!=t)
{
swap(a[u],a[t]);
down(t);
}
}
signed main()
{
cin>>n>>m;
r=n;
for(int i=1;i<=n;i++) cin>>a[i];
//建堆
for(int i=n/2;i>=1;i--) down(i);
while(m--)
{
cout<<a[1]<<" ";
a[1]=a[r--];
/*swap(a[1],a[size]);
size--;*/
down(1);
}
return 0;
}哈希表
哈希表根據(jù)處理哈希沖突的方式，又可以分為開放尋址法和拉鏈法。
模擬散列表
840. 模擬散列表 - AcWing題庫
1.拉鏈法
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int h[N],e[N],ne[N],idx;
void insert(int x)
{
int k=(x%N+N)%N;
e[idx]=x;//頭插法
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x)
{
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i])
{
if(e[i]==x) return true;
}
return false;
}
signed main()
{
int n;
cin>>n;
memset(h,-1,sizeof(h));
while(n--)
{
char op;
int x;
cin>>op>>x;
if(op=='I') insert(x);
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}?數(shù)學里-10%3=2，但在c++中結(jié)果是-1，負數(shù)模上一個數(shù)的結(jié)果是負數(shù)。
所以我們? ?(x%N+N)%N
?2.開放尋址法
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3,null=0x3f3f3f3f;
int h[N];
int find(int x)
{//如果在就返回他的位置，不在就返回他應該存儲的位子
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x)//如果坑位上有人
{
k++;
if(k==N) k=0;//循環(huán)從0開始
}
return k;
}
signed main()
{
int n;
cin>>n;
memset(h,0x3f,sizeof(h));
while(n--)
{
char op;
int x;
cin>>op>>x;
if(op=='I')
{
h[find(x)]=x;
}else{
if(h[find(x)]!=null) puts("Yes");
else puts("No");
}
}
return 0;
}字符串哈希
841. 字符串哈希 - AcWing題庫文章來源：http://www.zghlxwxcb.cn/news/detail-530468.html
這篇題解解釋得很好：AcWing 841. 字符串哈希 【公式助理解】 - AcWing文章來源地址http://www.zghlxwxcb.cn/news/detail-530468.html
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+10,P=131;
int n,m;
char str[N];
ULL h[N],p[N];
ULL get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
signed main()
{
cin>>n>>m>>str+1;
p[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=h[i-1]*P+str[i];
p[i]=p[i-1]*P;
}
while(m--)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(get(l1,r1)==get(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
} 到了這里，關于【算法基礎】數(shù)據(jù)結(jié)構的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
