微信网站开发教程视频教程百度官方免费下载安装
⩕ 单调栈
1、概念
对于一个栈，维持其单调性，有两种情况，单调递增栈：由栈底到栈顶单调递增
单调递减栈：由栈底到栈顶单调递减
2、核心模板（ 单调递增栈 ）
stack<int> stk;
void insert(int x)
{while(!stk.empty() && stk.top() > x)stk.pop();stk.push(x);
}3、应用
可用于找到一序列中某一元素一侧首个大于或小于它的元素
————————————————————————————
⩕ 单调队列
〇 单调队列
1、概念
对于一队列，维持其单调性，有两种情况，单调递增队列：从队尾到队头单调递增
单调递减队列：从队尾到队头单调递减
2、核心模板
deque<int> q;
void insert(int x)
{while(!q.empty() && q.back() < x)q.pop_back();q.push_back(x);
}〇 滑动窗口
1、概念
对一长为 n 的数组，有一长为 k（ k <= n ）的滑动窗口在其上滑动，且维持滑动窗口上的单调性
2、原理
设长为 n 的数组 a[n] ，
————————————————————————————
⩕ kmp算法
〇 寻找首个模式串
1、暴力解法（ BF ）
两重循环：i 循环主串 s ，j 循环模式串 t
在循环过程中 i ，j 会不断回溯，因此此解法效率低下
2、kmp优化原理
3、核心模板
void getnext(string &t)
{int i = 0;k = -1;next[0] = -1;while(i < t.size()){if(k == -1 || t[i] = t[k]) next[++i] = ++k;else k = next[k];}
}
int kmp(string &s , string &t)
{int i = 0,j = 0;while(i < s.size() && j < (int)t.size()){if(j == -1 || s[i] = t[j]) i++,j++;else j = next[j];}if(j == t.size()) return i - j;else return -1;
}4、深入分析
next数组中存的是模式串t 在与主串s 匹配失败时 模式串t 在当前失配位置可右移到的最大位置
如：模式串t A B C A B
t的下标 0 1 2 3 4
next数组 -1 0 0 0 1
若在第一个A处失配，则应回溯到模式串t 中 -1 的位置，但模式串t 中无该位置，即不回溯
若在第一个B处失配，则应回溯到模式串t 中 0 的位置，即第一个A处
若在第二个B处失配，则应回溯到模式串t 中 1 的位置，即第一个B处
. . . . . .
对前缀指针 k ，后缀指针 i ，其初始化分别为 k = -1，i = 0，其中 i 一直后移，若前后缀匹配成功则，i，k 均后移
对 i 的状态分析：i 一直后移并与 k 所指向的元素匹配，匹配成功时，i ，k 均后移，将此时 k 所指元素的位置存入next数组
匹配失败时，i 后移，k 回溯，将上一次匹配成功的位置存入next数组
对 k 的状态分析：1、k = -1 ： 初始状态 ，此时可看作 k 指向模式串外的一万能值，即可与任意值成功匹配，即 k = -1 时就视为匹配成功一次，此时 k 后移指向模式串t 中 t[0] ，即模式串中首个元素，模式串失配时即回溯到第一个元素
2、++k： 配对成功后 k 值更新，此时 k 可视作有两重含义，一是指向模式串t 中前缀元素的指针后移
二是模式串t 中前缀与后缀连续成功匹配的长度，且该长度为 k + 1
3、k = next[k]： k 匹配失败后回溯，回溯位数为 k + 1，即回溯到首个前后缀匹配成功的位置的前一位置，
连续成功匹配的长度可写作（ k + n ）+ 1，其中 k + n 表示 k 后移的过程，n 表示 k 后移的位数（ n = 1，2，3 ... ）
上式可写为 k + n + 1，即 k 是首个匹配成功的位置的前一位置，n + 1 即从该位置向后成功匹配的位数
故 k = next[k] 即回溯到了首个前后缀匹配成功的位置的前一位置
〇 优化next数组
1、情景
在某些情况下，next数组的处理效率并不是很高
如：主串s A A A B A A A A B
模式串t A A A A B
模式串t下标 0 1 2 3 4
next数组 -1 0 1 2 3
如上所示，设两个指针：i 指向主串s，j 指向模式串t 模式串t 在 j = 3 时与主串s 失配，依 next数组 此时指向 模式串t 的指针 j 应回溯到 t[2] ，然而易知 j = 2 时仍失配，此时 j 会回溯到 t[1] ，但 j = 1 时仍失配，此时 j 回溯到 t[0]
由上可知，next数组在上述情况中效率较低，在 j = 3 处失配时由于左侧均为重复元素，合理的操作应为直接回溯到 t[0] 即首个重复元素处
2、优化原理
增加一层判断，即判断相邻元素是否相同，相同则在对应的next数组的位置存入首个重复元素的位置
3、核心模板
void getnextval(int nextval[],string &t)
{int i = 0,k = -1;nexxtval[0] = -1;while(i < t.size() - 1){if(k == -1 || t[k] == t[i]){if(t[++k] != t[++i]) nextval[i] = k;else nextval[i] = nextval[k];}else k = nextval[k];}
}〇 寻找所有的模式串
1、前缀函数
用一长度为 m 的 Pi 数组表示，Pi[ i ] 表示 t[ 0 ... i ] 这个子串的最长公共前后缀的长度，则 Pi数组 与 next数组 有以下关系
Pi[ i ] = | next[ 1 ] = 0 , i = 0
| next[ i + 1 ] , i > 0
2、核心模板
vector<int> getPrefix(string &t)
{int m = t.size();vector<int> Pi(m);for(int i = 1;i < m;i++){int k = Pi[i - 1];while(k && t[k] != t[i]) k = Pi[k - 1]if(t[k] == t[i]) k++;Pi[i] = k;}return Pi;
}
vector<int> kmp(string &s,string &t)
{int n = s.size(),m = t.size();string r = t + '#' + s;Pi[m] = getPrefix( t );vector<int> res;for(int i = m + 1;i <= n + m;i++)if(Pi[i] == m) res.push_back(i - 2 * m);return res;
}〇 寻找所有的模式串
1、前缀函数
用一长度为 m 的 Pi 数组表示，Pi[ i ] 表示 t[ 0 ... i ] 这个子串的最长公共前后缀的长度，则 Pi数组 与 next数组 有以下关系
Pi[ i ] = | next[ 1 ] = 0 , i = 0
| next[ i + 1 ] , i > 0
2、核心模板
vector<int> getPrefix(string &t)
{int m = t.size();vector<int> Pi(m);for(int i = 1;i < m;i++){int k = Pi[i - 1];while(k && t[k] != t[i]) k = Pi[k - 1]if(t[k] == t[i]) k++;Pi[i] = k;}return Pi;
}
vector<int> kmp(string &s,string &t)
{int n = s.size(),m = t.size();string r = t + '#' + s;Pi[m] = getPrefix( t );vector<int> res;for(int i = m + 1;i <= n + m;i++)if(Pi[i] == m) res.push_back(i - 2 * m);return res;
}————————————————————————————
⩕ 并查集
1、应用
将两个集合合并，询问两个元素是否在同一集合中
2、基本原理
每个集合用一棵树表示。树根编号代表整个集合的编号，每个节点储存它的父节点，p[ x ] 表示 x 的父节点
3、实现原理
树根的判断：if( p[ x ] = x )
求 x 的集合编号：while( p[ x ] != x ) 从 x 开始一级级向上寻找其父节点，直到找到树根
合并集合：p[ x ] 是 x 集合的编号，p[ y ] 是 y 集合的编号，令 p[ x ] = y ,连接其树根即可合并两集合
4、核心模板
int find(int x) //找到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) //询问a，b是否在同一集合
{int pa = find(a);int pb = find(b);if(pa == pb) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}————————————————————————————
⩕ 模拟堆
1、概念
堆是储存数据的一种方式，可用完全二叉树表示
可分为两类，大根堆：根节点最大，向下递减
小根堆：根节点最小，向下递增
2、堆的核心操作
up：符合堆单调性的上浮
down：不符合堆单调性的下沉
堆的所有操作均可依靠上述两核心操作完成
3、堆的基础操作 （ 以小根堆为例 ）
堆排序
插入数据：在堆的尾部插入新数据，再排序，即 heap[++idx] = x; up(idx);
取最小值：最小值即 heap[1]
删除最小值：先删除堆顶元素，再将堆尾元素放至堆顶，再排序 heap[1] = heap[idx]; idx--; down(1);
删除任意元素
4、堆的储存方式
定义一 heap 数组进行储存，将 heap[ 1 ] 设为树根，若 heap[ x ] 为某一节点，则 heap[ 2*x ] 、heap[ 2*x+1]分别为其左右儿子节点,
5、核心模板
void down(int u)
{int t = u;if( 2*u <= idx && h[ 2*u ] < h[t] ) t = 2*u;if( 2*u + 1 <= idx && h[ 2*u + 1] < h[t]) t = 2*u + 1;if( u != t ) swap(h[u],h[t])
}
void up(int u)
{while( u/2 && h[u/2] > h[u]){swap(h[u],h[u/2])u/2;}
}欢迎订阅专栏，数据结构实验，期末大作业，前端后端，算法都有哦，想我发哪个方面的资源或文章可以私信我，免费的哦