铜山区建设局局网站,网站的规划和建设,经营网站挣钱,国外用python做的网站#x1f34e; 博客主页#xff1a;#x1f319;披星戴月的贾维斯 #x1f34e; 欢迎关注#xff1a;#x1f44d;点赞#x1f343;收藏#x1f525;留言 #x1f347;系列专栏#xff1a;#x1f319; 蓝桥杯 #x1f319;我与杀戮之中绽放#xff0c;亦如黎明的花… 博客主页披星戴月的贾维斯 欢迎关注点赞收藏留言 系列专栏 蓝桥杯 我与杀戮之中绽放亦如黎明的花朵 一起加油去追寻、去成为更好的自己 蓝桥杯倒计时 41天 文章目录、双指针算法、例题分析、AcWing字符串删减、AcWing最长连续不重复子序列、AcWing数组元素的目标和、AcWing判断子序列、总结提示以下是本篇文章正文内容下面案例可供参考 、双指针算法
、双指针算法的简单概念 双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。 、双指针算法的两个应用场景 两个指针i, j分别指向不同的序列。比如归并排序的合并过程。 两个指针i, j指向同一个序列。比如快速排序的划分过程。 、双指针算法的核心作用 将O(N^2)的时间复杂度优化成为O(N)相当于去掉了一层for循环。 、双指针算法的通用模板
for (int i 0, j 0; i n; i)
{while (j i check(i, j)) j;// 每道题目的具体逻辑
}双指针算法为什么能优化掉一层for循环 因为原来循环两次i,j我们是通过回溯的方式来实现遍历的即原来的内层循环j不满足条件时i, j 0开始循环。而双指针算法i, j都是具有单调性的一般是单调递增因此时间复杂度最多是O(n m)。 、例题分析
、AcWing字符串删减
本题链接: 字符串删减 简单分析题意对于长度为n的字符串我们删除一些字母使字符串中没用三个或者三个以上的连续的’x’,通过反证法我们可以得出在最优解中一定不会删掉’x’以外的字母。设置一个cnt 0, 来计算每一段x出现的次数,cnt 3, 操作次数 0 从cnt 3 ,要操作2次 双指针代码示例
#includeiostream
#includealgorithm
#includestring
using namespace std;
string str;
int n;
int main ()
{cin n str;int cnt 0, res 0;for(int i 0; i n; i)if(str[i] x){int j i 1;while(j n str[j] x) j;res max(j - i -2, 0);//如果长度小于0就和0取max,精妙的推算i j - 1;// i是要跳到j的位置但是i待会会,所以i j - 1}cout res endl;return 0;}模拟代码
#includeiostream
#includealgorithm
#includestring
using namespace std;
string str;
int n;
int main ()
{cin n str;int cnt 0, res 0;for(int i 0; i n; i)if(str[i] x){cnt;if(cnt 3){cnt - 1;res;}}else cnt 0;cout res endl;return 0;}、AcWing最长连续不重复子序列
本题链接: 最长连续不重复子序列 简单分析思路 代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 1e510;
int s[N],a[N];
int n;
int main()
{int res 0;cin n;for(int i 0; i n; i) cin a[i];for(int i 0, j 0; i n;i){s[a[i]];while(j i s[a[i]] 1){s[a[j]]--;j;}res max(res, i - j 1);}cout res endl;return 0;
}、AcWing数组元素的目标和
本题链接: 数组元素的目标和 简单分析思路本题属于两个指针i, j分别指向不同的序列。如果a[i] b[j] x时输出i和j我们从前往后枚举i从后往前枚举j如果两者的和x就j–,如果刚好等于就输出break如果小于就i。 代码示例
#includeiostream
#includealgorithm
using namespace std;const int N 1e5 10;
int a[N], b[N];
int n, m, x;
int main ()
{cin n m x;for(int i 0; i n; i) cin a[i];for(int i 0; i m; i) cin b[i];for(int i 0, j m - 1; i n; i){while(a[i] b[j] x j 0){j--;}if(a[i] b[j] x){cout i j endl;break;}}return 0;
}、AcWing判断子序列
本题链接: 判断子序列 代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 1e6 10;
int a[N], b[N];
int n, m;
int main ()
{cin n m;for(int i 0; i n; i) cin a[i];for(int i 0; i m; i) cin b[i];int i 0, j 0;while(i n j m){if(a[i] b[j]) i;j;}if(i n) printf(Yes);else printf(No);return 0;
}、总结 本文简要介绍了双指针的简要概念和几道双指针的经典例题希望大家读后能有所收获
