wordpress仿站header,中工信融营销型网站建设,windows版本的wordpress,如何查看实时街景地图目录
双指针简介
对撞指针
求解步骤
例题 蓝桥oj1371回文判定
题目描述
输入描述
输出描述
输入输出样例
示例 1
示例 2
运行限制
解
快慢指针
求解步骤
例题 蓝桥oj1372美丽的区间
题目描述
输入描述
输出描述
输入输出样例
示例 1
运行限制
解
例题 蓝…目录
双指针简介
对撞指针
求解步骤
例题 蓝桥oj1371回文判定
题目描述
输入描述
输出描述
输入输出样例
示例 1
示例 2
运行限制
解
快慢指针
求解步骤
例题 蓝桥oj1372美丽的区间
题目描述
输入描述
输出描述
输入输出样例
示例 1
运行限制
解
例题 蓝桥oj 1621挑选字串
题目描述
输入描述
输出描述
输入输出样例
示例
运行限制
解 双指针简介
双指针算法是一种常用的算法技巧它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作
双指针并非真的用指针实现一般用两个变量来表示下标(在后面都用指针来表示)
双指针算法使用两个指针在数据结构上进行迭代并根据问题的要求移动这些指针。
双指针往往也和单调性、排序联系在一起在数组的区间问题上暴力法的时间复杂度往往是O(n^2)的但双指针利用“单调性”可以优化到O(n)。
常见的双指针有对撞指针和快慢指针
对撞指针
指的是两个指针 left、right(简写为1,r)分别指向序列第一个元素和最后一个元素
然后1指针不断递增r不断递减直到两个指针的值相撞或错开(即1r)或者满足其他要求的特殊条件为止。
对撞指针一般用来解决有序数组或者字符串问题(常见于区间问题)
查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题
字符串反转问题:反转字符串、回文数、颠倒二进制等问题。
求解步骤
1.使用两个指针left、right。left指向序列第一个元素即left1right指向序列最后一个元素即rightn。
2.在循环体中左右指针相向移动当满足一定条件时将左指针右移left。当满足零一条件时将右指针左移right--
3.知道两指针相撞即leftright或者满足其他要求的特殊条件时跳出循环体。
例题 蓝桥oj1371回文判定
题目描述
给定一个长度为 nn 的字符串 SS。请你判断字符串 SS 是否回文。
输入描述
输入仅 11 行包含一个字符串 SS。
1≤∣S∣≤1061≤∣S∣≤106保证 SS 只包含大小写、字母。
输出描述
若字符串 SS 为回文串则输出 YY否则输出 NN。
输入输出样例
示例 1 输入 abcba输出 Y示例 2 输入 abcbb输出 N运行限制
最大运行时间1s最大运行内存: 128M
解
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N 1e6 9;
char s[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin s 1;int n strlen(s 1);int l 1, r n;bool ans true;while (l r ans){if (s[l] ! s[r])ans false;l, r--;}cout (ans ? Y : N) endl;return 0;
}
快慢指针
快慢指针一般比对撞指针更难想也更难写
指的是两个指针从同一侧开始遍历序列且移动的步长一个快一个慢。
移动快的指针被称为快指针移动慢的指针被称为慢指针。
为了方便理解我们成快指针为r慢指针为1这样慢指针和快指针构成区间[1,r]。
两个指针以不同速度、不同策略移动直到快指针移动到数组尾端或者两指针相交或老满足其他特殊条件时为止。
求解步骤
1、使用两个指针l、r。l一般指向序列的第一个元素即l1r一般指向序列第零个元素即r0.即初始时区间[1,r] [1,0]表示空区间
2、在循环体中将左右指针向右移动。当满足一定条件时将慢指针右移即l。当满足另外一定条件时也可能不需要满足条件将指针右移即r保持[l,r]为合法区间。
3、到指针移动到数组尾端时即ln且rn或者两指针相交或者满足其他特殊条件时跳出循环体。
例题 蓝桥oj1372美丽的区间
题目描述
给定一个长度为 nn 的序列 a1,a2,⋯ ,ana1,a2,⋯,an 和一个常数 SS。
对于一个连续区间如果它的区间和大于或等于 SS则称它为美丽的区间。
对于一个美丽的区间如果其区间长度越短它就越美丽。
请你从序列中找出最美丽的区间。
输入描述
第一行包含两个整数 n,Sn,S其含义如题所述。
接下来一行包含 nn 个整数分别表示 a1,a2,⋯ ,ana1,a2,⋯,an。
10≤N≤10510≤N≤1051×ai≤1041×ai≤1041≤S≤1081≤S≤108。
输出描述
输出共一行包含一个整数表示最美丽的区间的长度。
若不存在任何美丽的区间则输出 00。
输入输出样例
示例 1 输入 5 6
1 2 3 4 5输出 2运行限制
最大运行时间1s最大运行内存: 128M
解
#includeiostream
#includealgorithm
#includecstring
using namespace std;const int N 1e5 9;
int a[N], S;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, S; cin n S;int ans n 1;for (int i 1; i n; i)cin a[i];for (int i 1,j 0,sum 0; i n; i){//考虑移动j即j because ij说明区间不合法while (i j || (j 1 n sum S))sum a[j];if (sum S)ans min(ans, j - i 1);sum - a[i];}cout (ansn?0:ans) endl;return 0;
}
例题 蓝桥oj 1621挑选字串
题目描述
有 n 个数和一个整数 m。
现要从这 n 个数选出一个连续子串要求这个字串里面至少有 k 个数要大于等于 m。
问一共能选出多少个子串显然子串长度要大于等于 k。
输入描述
输入第一行是 3 个整数 n、m、k。
输入第二行是 n 个整数 a1、a2、⋯、an表示序列。
2≤n≤20001≤k≤n21≤m,ai≤109 2≤n≤20001≤k≤2n1≤m,ai≤109。
输出描述
输出一个整数表示答案。
输入输出样例
示例 输入 7 4 2
4 2 7 7 6 5 1输出 18运行限制
最大运行时间1s最大运行内存: 256M
解
#includeiostream
#includealgorithm
#includecstring
using namespace std;const int N 2e55;
int a[N];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m, k; cin n m k;for (int i 1; i n; i)cin a[i];int ans 0;for (int i 1, j 0, count 0; i n; i){while (i j || (j 1 n count k))//j在i的左边或者m的数量小于k{j;count (a[j] m);}if (count k)ans (n - j 1);count - (a[i] m);}cout ans endl;return 0;
}
