单链表
思路：
工程链表：
typedef struct SListNode { int data; // val struct SListNode* next; // 存储下一个节点的地址 }SLN;
算法表示法：
head 表示头结点的下标，数组e[]表示链表 date值，ne[]表示存储下一个节点的地址的指针next，idx 存储当前已经用到了哪个点
#include <iostream> using namespace std; const int N = 100010; // head 表示头结点的指针 // e[i] 表示节点i的值 // ne[i] 表示节点i的next指针是多少 // idx 存储当前已经用到了哪个点,工程链表中的新地址 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; //-1表示指向空 idx = 0; //下标索引从0开始 } // 将x插到头结点 void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx ++ ; } // 将x插到下标是k的点后面 void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ; } // 将下标是k的点后面的点删掉 void remove(int k) { ne[k] = ne[ne[k]]; //让结点直接指向下一个结点的next，不用管内存泄漏 } int main() { int m; cin >> m; init(); while (m -- ) { int k, x; char op; cin >> op; if (op == 'H') { cin >> x; add_to_head(x); } else if (op == 'D') { cin >> k; if (!k) head = ne[head]; //如果k为0，删除头结点，ne[head]表示头结点的下一节点 else remove(k - 1); //k-1对应从0开始的idx } else { cin >> k >> x; add(k - 1, x); } } for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; cout << endl; return 0; }
双链表
思路：
与单链表类似，e[N]存值，l[N]、r[N]表示左右指针
双链表初始化：
0号店表示头结点，1号表示尾节点
r[0] = 1, l[1] = 0; idx = 2;
删除节点a的remove（）函数
void remove(int a) { l[r[a]] = l[a]; r[l[a]] = r[a]; } //先内层再到外层
在节点k的右边插入一个数x方法
第一步：开一个新节点，左右指针指向k，与k的下一个节点
第二步：先让k的下一个节点的左指针指向新点，再用k的右指针指向新点；顺序搞错会导致数据覆盖
void insert(int a, int x) { e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; }
#include <iostream> using namespace std; const int N = 100010; int m; int e[N], l[N], r[N], idx; // 在节点a的右边插入一个数x void insert(int a, int x) { e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; } // 删除节点a void remove(int a) { l[r[a]] = l[a]; r[l[a]] = r[a]; } int main() { cin >> m; // 0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; while (m -- ) { string op; cin >> op; int k, x; if (op == "L") { cin >> x; insert(0, x); } else if (op == "R") { cin >> x; insert(l[1], x); } else if (op == "D") { cin >> k; remove(k + 1); //idx从2开始，插入节点夹在head与tail之间 } else if (op == "IL") { cin >> k >> x; insert(l[k + 1], x); } else { cin >> k >> x; insert(k + 1, x); } } for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' '; cout << endl; return 0; }
模拟栈
#include <iostream> using namespace std; const int N = 100010; int st[N]; int top,n; int main() { cin>>n; while(n--) { string s; cin>>s; if(s=="push") { int a; cin>>a; st[++top]=a; } else if(s=="pop") { --top; } else if(s=="query") { cout<<st[top]<<endl; } else if(s=="empty") { cout<<(top==0?"YES":"NO")<<endl; } } return 0; }
表达式求值模板
#include<iostream> #include<stack> #include<unordered_map> using namespace std; stack<int> num; stack<char> op; unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}};//数值表示优先级 void eval() { int a=num.top(); num.pop(); int b=num.top(); num.pop(); char p=op.top(); op.pop(); int r=0; if(p=='+') r=b+a; if(p=='-') r=b-a; if(p=='*') r=b*a; if(p=='/') r=b/a; num.push(r); } int main() { string s; cin>>s; for(int i=0;i<s.size();i++) { if(isdigit(s[i]))//如果是数字则转化入栈 { int x=0,j=i; while(j<s.size()&&isdigit(s[j])) { x=x*10+s[j]-'0'; j++; } num.push(x); i=j-1; } else if(s[i]=='(') { op.push(s[i]); } else if(s[i]==')')//遇到右括号直接操作括号里的 { while(op.top()!='(') eval(); op.pop(); } else { //前一个符号优先级不小于当前符号，说明可以计算后再加入当前符号 while(op.size()&&h[op.top()]>=h[s[i]]) eval(); op.push(s[i]); } } while(op.size()) eval(); cout<<num.top()<<endl; return 0; }
模拟队列
#include<iostream> using namespace std; const int N=1e5+10; int q[N]; int main() { int n; cin>>n; int hh=0,tt=0; while(n--) { string op; int x; cin>>op; if(op=="push") { cin>>x; q[tt++]=x; } else if(op=="pop") hh++; else if(op=="empty") { if(hh<tt) puts("NO"); else puts("YES"); } else cout<<q[hh]<<endl; } return 0; }
单调栈
cin，cout速度大幅提高方法：
cin.tie(0); ios::sync_with_stdio(false);
#include <iostream> using namespace std; const int N = 100010; int stk[N], tt; int main() { //cin.tie(0); // ios::sync_with_stdio(false); int n; cin >> n; while (n -- ) { int x; cin>>x; while (tt && stk[tt] >= x) tt -- ; //不符合，出栈 if (!tt) cout<<"-1"<<" "; else cout<<stk[tt]<<" "; stk[ ++ tt] = x; //当前值入栈，与下一个数比较 } return 0; }
单调队列&滑动窗口
思路：
利用双端队列思想
设 队列q[hh],q[tt]分别表示窗口左边界（队头）与右边界（队尾），存储下标
用 i 表示窗口进程，则窗口范围【i-k+1,i】
（先求最小值）根据滑动窗口性质，队头的数会先消失，如果队尾插入的值比前一个数小，则前数不是最小值，所以直到出窗口也不会被输出
核心操作：如果队尾插入的值比前一个数小，那么将前一个数移出队列，最终队列会形成单调递增，取最小值永远在q[hh]处取
#include <iostream> using namespace std; const int N = 1000010; int a[N], q[N]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); int hh=0,tt=-1;//分别表示左边界和右边界 for(int i=0;i<n;i++) { if(hh<=tt&&i-q[hh]+1>k) hh++; while(hh<=tt&& a[q[tt]]>=a[i]) tt--;//不符合单增 q[++tt]=i;//先看前面元素与当前值是否构成单增再入队 if(i>=k-1) cout<<a[q[hh]]<<" ";//始终确保q[hh]为最小值，即单调递增序列 } puts(""); hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) { if (hh <= tt && i - k + 1 > q[hh]) hh ++ ; while (hh <= tt && a[q[tt]] <= a[i]) tt -- ; //对于最大值，直接改为单调递减即可 q[ ++ tt] = i; if (i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); return 0; }
KMP字符串
一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。
------- KMP
#include<iostream> using namespace std; const int N=100010,M=1000010; char q[N],s[M]; int ne[N];//保存next数组 int main() { int n,m; cin>>n>>q+1>>m>>s+1;//下标均从1开始 for(int i=2,j=0;i<=n;i++) //j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始 { while(j&&q[i]!=q[j+1]) j=ne[j]; //如果不行可以换到next数组 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数组中的值 if(s[i]==q[j+1]) j++; //匹配成功了,那么j就加1,继续后面的匹配 if(j==n)//如果长度等于n了,说明已经完全匹配上去了 { printf("%d ",i-j); //因为题目中的下标从0开始,所以i-j不用+1; j=ne[j]; //为了观察其后续是否还能跟S数组后面的数配对成功 } } return 0; }
