高端外贸网站建设,杭州室内设计培训,四海网络网站建设建站,wordpress自适应建站作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;或许会很慢#xff0c;但是不可以停下来#x1f43e; 文章目录1.双指针分类2.双指针思想3.双指针应用1.双指针分类
常见问题分类
(1) 对于一个序列#xff0c;用两个指针维护一段区间, 比如快速排序。 … 作者指针不指南吗 专栏算法篇 或许会很慢但是不可以停下来 文章目录1.双指针分类2.双指针思想3.双指针应用1.双指针分类
常见问题分类
(1) 对于一个序列用两个指针维护一段区间, 比如快速排序。 (2) 对于两个序列维护某种次序比如归并排序中合并两个有序序列的操作。这种情况比较多 2.双指针思想
//朴素算法
for(int i0;in;i)for(int j0;jn;j)······//每道题的具体逻辑将上面朴素算法的 O( n2n^2n2 ) 优化为 O( n )
for (int i 0, j 0; i n; i )
{while (j i check(i, j)) j ;// 具体问题的逻辑
}所以可以想出朴素算法然后用双指针算法做出优化 3.双指针应用
例题1.
单独输出单词 输入一个字符串把里面的每个单词输出出来,每个单词之间用空格隔开。 思路 一个指针 i 指向单词的开头另一个指针 j 指向单词的结尾。 先枚举 i ,然后让 j 指向 i 即单词开头j, 直到遇到空格表示这个单词结束。 输出一个单词结束之后记得让 i j ,更新 i , 跳过当前单词进入下一个的单词开头。 代码实现
#includebits/stdc.h
using namespace std;int main()
{char s[100010]; //输入一个字符串gets(s);int nstrlen(s);for(int i0;in;i){ // 枚举i,i表示一个单词的开头int ji; while(jns[j]! ) j; //j表示单词的结尾即不超过字符串的长度遇到空格表示一个单词结束//这道题的具体逻辑 for(int ki;kj;k) couts[k]; //输出单词coutendl;ij; //令 i 跳过已经输出的单词}return 0;
}例题2.
最长连续不重复子序列 给定一个长度为 n 的整数序列请找出最长的不包含重复的数的连续区间输出它的长度。 输入格式 第一行包含整数 n。 第二行包含 n 个整数均在 0∼105 范围内表示整数序列。 输出格式 共一行包含一个整数表示最长的不包含重复的数的连续区间的长度。 数据范围 1≤n≤105 输入样例 5
1 2 2 3 5输出样例 3思路 枚举 i 表示区间右端点的指针 , j 表示区间左端点的指针 利用区间内数字出现的个数来判断是否满足条件 i 向前走一步a [ i ] 所表示的数出现的次数多一次用 s 数组把数字出现的次数存起来 j 从 0 开始走如果在 i 走的过程中 s [ a [ i ] ] 1则说明 i 现在表示的数与之前的重复了 让 j 往前走区间挤出去一个数先 s [ a [ j ] ] --再 j , 直到把重复的数挤出去即 s [ a [ i ] ] 1; i 每走一步判断一下区间大小是否做出最大值 res 更新 代码实现 #includebits/stdc.h
using namespace std;const int N100010;
int n;
int a[N],s[N]; //a表示原整数序列s 表示区间内数字出现的次数int main()
{cinn;for(int i0;in;i) cina[i]; //读入数据int res0,i0,j0; //res 表示最大的区间大小for(i0;in;i){s[a[i]]; //i前进区间内a[i]的出现次数增加while(s[a[i]]1){ //若出现重复元素则进入循环s[a[j]]--; //j前进a[j]出现次数减少一次j;}resmax(res,i-j1); //更新最大值}coutres;return 0;
}
