🏝️专栏： 【蓝桥杯备篇】
🌅主页： f狐o狸x
"今天熬的夜，会变成明天奖状的闪光点！"
目录
一、唯一的雪花
题目链接
题目描述
解题思路
解题代码
二、逛画展
题目链接
题目描述
解题思路
解题代码
三、字符串
题目链接
题目描述
解题思路
解题代码
四、丢手绢
题目链接
题目描述
解题思路
解题代码
喵~ 今天要学习的算法是双指针，也被称为滑动窗口是⼀种优化暴⼒枚举策略的⼿段：
• 当我们发现在两层 for 循环的暴⼒枚举过程中，两个指针是可以不回退的，此时我们就可以利⽤两个指针不回退的性质来优化时间复杂度。
一、唯一的雪花
题目链接
UVA11572 唯一的雪花 Unique Snowflakes
题目描述
解题思路
例如题目中给的输入样例，我们可以按照以下方法来搞定此题：
第一步：先初始化左右指针
第二步：通过右指针向前走开始进窗口
第三步：通过题意判断出窗口
第四部：更新结果，重复上述步骤，直到遍历完全部数组
解题代码
#include <iostream>
#include <unordered_map>using namespace std;typedef long long LL;const int N = 1e6 + 10;int n;
LL a[N];int main()
{int T; cin >> T;while (T--){cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];// 初始化int left = 1, right = 1, ret = 0;unordered_map<int, int> mp;while (right <= n){// 进窗口mp[a[right]]++;// 判断while (mp[a[right]] > 1){mp[a[left]]--;left++;}// 更新结果ret = max(ret, right - left + 1);right++;}cout << ret << endl;}return 0;
}二、逛画展
题目链接
P1638 逛画展 - 洛谷
题目描述
解题思路
这题其实就是给你一串数字，让你找到包括所有数字种类的最小子串
解题代码
#include <iostream>using namespace std;const int N = 1e6 + 10;int a[N], mp[N];int n, m;int kind;int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];// 初始化int left = 1, right = 1,begin = 1 , ret = n;while (right <= n){// 进窗口if (mp[a[right++]]++ == 0) kind++;// 判断while (kind == m){// 更新结果int len = right - left ;if (len < ret){ret = len;begin = left;}// 出窗口if (mp[a[left++]]-- == 1) kind--;}}cout << begin << " " << begin + ret - 1 << endl;return 0;
}三、字符串
题目链接
字符串
题目描述
解题思路
这题和上一题是一样的，只是把数字改成字符串了
解题代码
#include <iostream>using namespace std;const int N = 30;int mp[N];
int kind;int main()
{string s; cin >> s;int n = s.size();// 初始化int left = 0, right = 0, ret = n;while(right < n){// 进窗口if(mp[s[right++] - 'a']++ == 0) kind++;// 判断while(kind == 26){// 更新结果int len = right - left;ret = min(ret, len);// 出窗口if(mp[s[left++] - 'a']-- == 1) kind--;}}cout << ret << endl;return 0;
}四、丢手绢
题目链接
丢手绢
题目描述
解题思路
这个题依然可以用双指针来解决，只不过是从一条直线变成了一个环而已
解题代码
#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n;int main()
{cin >> n;LL sum;for(int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];}LL mid = sum / 2;// 初始化LL left = 1, right = 1, ret = 0, len = 0;while(right <= n){// 进窗口if(len <= mid) {len += a[right++];}// 判断while(len > mid){// 更新结果ret = max(sum - len, ret);// 出窗口len -= a[left++];}if(ret > mid) ret = sum - ret;ret = max(ret, len);}cout << ret << endl;return 0;
}总之，对于双指针这类型的题目就四步：1. 初始化 2. 进窗口 3. 判断出窗口 4. 更新结果
明天我们将学习二分算法，感兴趣的朋友记得关注我哟~
886~
"今天的bug是明天的经验值"
