说在前面
最近快要期末了所以咕咕咕了好久，但是学早就学好了，只是一直没更新。
为了日后更好的写自己的博客，顺便学习了一点点markdown语法，希望观感会更好一点。
我是小白，如果有发现文章有不对的地方，还请指正，谢谢。
接下来的博客我打算花更多的篇幅在分析知识点（主要是自己学不太明白的）上面（毕竟书上其他博客都有题解）
接下来是正文
0X11 栈
这是其中一种基础的数据结构，我们不但要学会用STL，也要学会用数组模拟
只需要一个参数tt来表示栈顶的指针即可
根据书中，栈有以下几种应用：
1.表达式的计算：
电脑习惯计算的是后缀表达式，我们人类习惯看中缀表达式。那么假如给我们一个中缀表达式，我们需要将他转化为后缀表达式才可以。
（题目）中缀表达式的计算
具体的代码可以看题解，这里不多做解释，书上也讲解了方法。
2.单调栈：
这个很重要，先给出单调栈的经典例题直方图中最大的矩形
题目的思路：我们注意到，假如从中间的一个矩形开始向两边扩展，如果需要求到最大的一个的话，就是说要尽量的扩展开来。
那么什么时候扩展不开了呢？等到扩展到的这个矩形没有当前的高就停止。
那么我们可以想到一个朴素算法，就是一个一个枚举矩形，然后向两边扩展
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL h[N];
int n;
int main() {
while (cin >> n, n) {
LL ans = 0;
h[0] = -1;
for (int i = 1; i <= n; i ++ ) scanf("%lld", &h[i]);
for (int i = 1; i <= n; i ++ ) {
LL len = 1;
for (int j = i + 1; j <= n; j ++ ) {
if (h[j] >= h[i]) len ++ ;
else break;
}
for (int j = i - 1; j; j -- ) {
if (h[j] >= h[i]) len ++ ;
else break;
}
ans = max (ans, len * h[i]);
}
cout << ans << endl;
}
return 0;
}
那么这个算法如何优化呢？
我们的目标是找到每个矩形的左右能扩展的边界即可，我们把\(L_i\)和\(R_i\)记作i号矩形的左右边界。
那么该矩形能扩展到的边界就是(\(R_i - L_i\) + 1) \(\times\) \(h_i\) .
我们只要找到L和R就行了
这个问题就相当于给你一个数组h，找到第一个小于h[i]的左边界和右边界。
这就是一个单调栈问题。
我们拿一个栈来存从左到右遍历过的矩形。
按照样例，我们从左到右编号1~7，假设我们找到了5号矩形，并且我们从它的左边找左边界。那么我们发现1号矩形是没什么用的
因为有2号矩形在，它就永远不会被作为后面矩形的左边界，因此我们把他去掉。
所以，这个栈应该这么维护：遍历矩形高度，假如当前高度为p，如果p小于等于h[栈顶元素]，就让栈顶出栈，直到空栈或者p大于h[栈顶]即可。
最后栈顶的那个元素就是p的左边界了，将p的下标入栈。
反过来遍历就能得到右边界。
于是这个栈内元素就是单调的了，也就是单调栈。
这个过程中，每个高度最多被入栈一次、出栈一次，因此复杂度为O(2n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL h[N];
LL L[N], R[N];
int n;
int main() {
stack<int> sta;
while (cin >> n, n) {
while (!sta.empty()) sta.pop();
h[0] = -1;
sta.push(0);
for (int i = 1; i <= n; i ++ ) scanf("%ld", &h[i]);
//计算左边界
for (int i = 1; i <= n; i ++ ) {
int p = h[i];
while (!sta.empty() && p <= h[sta.top()]) sta.pop();
if (!sta.empty()) L[i] = sta.top();
else L[i] = i;
sta.push(i);
}
//计算右边界
while (!sta.empty()) sta.pop();
h[n + 1] = -1, sta.push(n + 1);
for (int i = n; i; i -- ) {
int p = h[i];
while (!sta.empty() && p <= h[sta.top()]) sta.pop();
if (sta.empty()) R[i] = i;
else R[i] = sta.top();
sta.push(i);
}
LL ans = 0;
for (int i = 1; i <= n; i ++ ) {
ans = max(ans, (R[i] - L[i] - 1) * h[i]);
}
cout << ans << endl;
}
return 0;
}
这就是单调栈，难点主要是能不能想到这个模型
0X12 队列
队列有以下几种应用
1.BFS，最短路等
2.单调队列：
滑动窗口
题解比较详尽了，这里放个代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int main() {
deque<int>q;
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
if (!q.empty() && i - k + 1 > q.front()) q.pop_front();
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0)cout << a[q.front()] << " ";
}
puts("");
while (!q.empty()) q.pop_back();
for (int i = 0; i < n; i++) {
if (!q.empty() && i - k + 1 > q.front()) q.pop_front();
while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
q.push_back(i);
if (i - k + 1 >= 0) cout << a[q.front()] << " ";
}
return 0;
}
最大子序和
这题的讲解比较书上比较详细，就不再多说了。
0X13 链表和邻接表
这个主要是记住模板，反正我已经敲的比较熟了
void add(int a, int b) {
val[idx] = b, nex[idx] = h[a], h[a] = idx ++ ;
}
0X14 && 0X15 Hash 与 字符串
-
到这里就比较痛苦了，不过我先理一下这里都讲了啥知识点啊
1.用邻接表来建立散列表（哈希表）
2.字符串哈希
3.Manacher算法
4.字符串的最小表示法
5.KMP字符串匹配 -
一个一个来，先看第一个
-
1.哈希表的建立
利用邻接表即可，注意我们定义哈希函数时候的数字需要用质数。
模拟散列表 -
2.字符串哈希
这个是重点，用一道模板题来解释
兔子兔子与兔子
#include<iostream>
using namespace std;
typedef unsigned long long ULL;//自动对2^64取余
const int N=1e6+10,P=131;//最好定为131或13331，这样冲突的概率最小
char ch[N];
ULL n,h[N],p[N];
int main(){
scanf("%s",ch+1);
cin>>n;
p[0]=1;
for(int i=1;ch[i];i++){
h[i]=h[i-1]*P+ch[i];
p[i]=p[i-1]*P;
}
while(n--){
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
if(h[r1]-h[l1-1]*p[r1-l1+1]==h[r2]-h[l2-1]*p[r2-l2+1])puts("Yes");//将比较过程通过字符串hash直接简化为O(1)。
else puts("No");
}
return 0;
}
- 3.Manacher算法
- 4.字符串的最小表示
给出模板以及例题
项链
这个算法主要是由朴素算法优化而来，朴素算法容易推出是这样的：
int k = 0, i = 0 ,j = 1;
//len表示字符串长度
while(k < len && i < len && j < len){
if(a[(i + k) % len] == a[(j + k) % len]) k ++ ;
else {
if(a[(i + k) % len] > a[(j + k) % len]) i ++ ;
else j ++ ;
if(i == j) i ++ ;
k = 0;
}
}
int ans1 = min(i, j);//ans1为最小表示的起点
然后优化一下（很容易推出来的）
int k = 0, i = 0 ,j = 1;
//len表示字符串长度
while(k < len && i < len && j < len){
if(a[(i + k) % len] == a[(j + k) % len]) k ++ ;
else {
if(a[(i + k) % len] > a[(j + k) % len]) i = i + k + 1;
else j = j + k + 1;
if(i == j) i ++ ;
k = 0;
}
}
int ans1 = min(i, j);//ans1为最小表示的起点
- 5.KMP字符串匹配
难点在理解next数组的含义，这里给出模板
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m;
int ne[N];
char p[N],s[M];
int 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 - n << " ";
j = ne[j];
}
}
return 0;
}
我所理解的next数组的含义：在同一字符串中，next[i]表示与以i为结尾的某个后缀字符相匹配的前缀的最大长度
模板题
0X16 Trie字典树
对于字符串的查找，还有一些位运算题目有奇效
给出模板
int son[N][26],cnt[N],idx;//son[x][y]表示x之后的y的值是多少（用idx计数）
void Insert(char s[]) {//插入
int p = 0;
for (int i = 0; s[i]; i++) {
int tmp = s[i] - 'a';
if (!son[p][tmp]) son[p][tmp] = ++idx;
p = son[p][tmp];
}
cnt[p]++;
}
int query(char s[]) {//查询是否存在
int p = 0;
for (int i = 0; s[i]; i++) {
int tmp = s[i] - 'a';
if (!son[p][tmp]) return 0;
p = son[p][tmp];
}
return cnt[p];
}
0X17 二叉堆
这个虽然STL有优先队列，但是也要学会自己写，书上有模板，这里就不写了
还有一个重要的应用，就是哈夫曼树
哈夫曼树模板知识点就这么多了，但是题目还是要一题一题练的，加油。
京公网安备 11010502036488号