海南建设培训网站,wordpress 链接微博,佛山百度推广电话,联盟网站做任务⩕ 单调栈
1、概念
对于一个栈#xff0c;维持其单调性#xff0c;有两种情况#xff0c;单调递增栈#xff1a;由栈底到栈顶单调递增
单调递减栈#xff1a;由栈底到栈顶单调递减
2、核心模板#xff08; 单调递增栈 #xff09;
stackint stk;
void …⩕ 单调栈
1、概念
对于一个栈维持其单调性有两种情况单调递增栈由栈底到栈顶单调递增
单调递减栈由栈底到栈顶单调递减
2、核心模板 单调递增栈
stackint stk;
void insert(int x)
{while(!stk.empty() stk.top() x)stk.pop();stk.push(x);
}
3、应用
可用于找到一序列中某一元素一侧首个大于或小于它的元素
————————————————————————————
⩕ 单调队列
〇 单调队列
1、概念
对于一队列维持其单调性有两种情况单调递增队列从队尾到队头单调递增
单调递减队列从队尾到队头单调递减
2、核心模板
dequeint 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 -1i 0其中 i 一直后移若前后缀匹配成功则ik 均后移
对 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 123 ...
上式可写为 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 指向主串sj 指向模式串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、核心模板
vectorint getPrefix(string t)
{int m t.size();vectorint 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;
}
vectorint kmp(string s,string t)
{int n s.size(),m t.size();string r t # s;Pi[m] getPrefix( t );vectorint 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、核心模板
vectorint getPrefix(string t)
{int m t.size();vectorint 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;
}
vectorint kmp(string s,string t)
{int n s.size(),m t.size();string r t # s;Pi[m] getPrefix( t );vectorint 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) //询问ab是否在同一集合
{int pa find(a);int pb find(b);if(pa pb) coutYESendl;else coutNOendl;
}
————————————————————————————
⩕ 模拟堆
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*x1]分别为其左右儿子节点,
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;}
}
欢迎订阅专栏数据结构实验期末大作业前端后端算法都有哦想我发哪个方面的资源或文章可以私信我免费的哦
