双指针是算法中常见的处理方式。
在处理线性的题目时，通常会有提到另外的说法，滑动窗口（或尺取）。
以常见的字符串为例，我们设定两个指针，左指针left，右指针right当两个指针都确定了在串中的位置，则可以截取一个字串。我们可以把它比作是一个窗口，而当两个指针进行移动的时候，那这个窗口也就滑动了。
下面我将以例题驱动讲解算法思路和实现过程。(C++描述)
常见题目分析
- 存在一个指定序列
- 是否指定
子序列长度
- 确定长度，
固定窗口 - 不确定长度，但有范围，
不定长窗口
- 需要对子序列进行访问和操作
- 只有当我们处理完所有子序列时才能保证获得最终答案
这些题目通常都比较模板，不同点往往在于 不同题对子序列的不同处理需求
固定窗口型是不定长窗口型的学习基础，当然思路和实现也比较简单
固定窗口
例题 ：力扣：239. 滑动窗口最大值
题意：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
这题虽然时hard题，但是却是hard中的easy题，连很多中等题的难度都达不到。要是还是怕，后面我会放同类型的easy和normal题来先练习。
分析：
需要一种数据结构满足以下条件
- 能够存储子序列的所有值
- 能够方便的
移除left和加入right - 能够获得该数据结构中的
最值
一般来说我们会优先想到set map priority_queue这三类。
但priority_queue无法直接移除left， set无法记录重复的值。
因为我们可以使用map处理，key存放数值，value记录出现次数
但在C++中有multiset这么一种可以记录重复数据的特殊set因此以下代码将以multiset来展示。
实现：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
multiset<int, greater<int>> mst;
for (int i = 0; i < n && i < k; i++) {
mst.insert(nums[i]);
}
vector<int>ans;
ans.push_back(*mst.begin());
for (int right = k; right < n; right++) {
int left = i-k;
auto it = mst.find(nums[left]);
mst.erase(it);
mst.insert(nums[right]);
ans.push_back(*mst.begin());
}
return ans;
}
};
相关练习：
力扣：219. 存在重复元素 II
力扣：567. 字符串的排列
不定长窗口
例题：牛客：智乃的密码
题目描述：
智乃去注册账号，他发现网站的的密码必须符合以下几个条件
-
? 密码是仅包含大小写英文字母、数字、特殊符号的字符串。 -
? 密码的长度不少于L个字符，并且不多于R个字符。 -
? 密码中应该至少包括①大写英文字母、②小写英文字母、③数字、④特殊符号这四类字符中的三种。 所谓特殊字符，是指非大小写字母、数字以及空格回车等不可见字符的可见字符，包括但不限于"~!@#$%^&*()_+"。 现在智乃有一个长度大小为N的字符串S，她想知道S串中有多少个子串是一个符合条件的密码，请你帮助智乃统计符合条件的密码数目。 子串是指字符串中某一段连续的区间，例如对于字符串"abcde"来说，“abc”,"cde"都是它的子串，而"ace"不是它的子串。
输入描述:
第一行输入三个正整数N,L,R(1≤N≤10^5,1≤L≤R≤N)表示S串的长度，合法密码长度应该在L到R个字符之间。
接下来一行输入一个长度为N的字符串S，字符串仅包括①大写英文字母、②小写英文字母、③数字、④特殊符号四类字符。
输出描述
仅一行一个整数，表示有多少子串是一个合法的密码。
示例1
输入
10 6 8
asdfeg111*
输出
3
说明
“eg111*”
“feg111*”
“dfeg111*”
该题出自 2022牛客寒假算法基础集训营3 （付费比赛）可能要付费才能做
以后会寻找更好的免费题来替换
分析： 这题还好没有玩什么文字游戏和考验语文阅读能力
串中的每个字符可以划分为4种状态，因为可以预处理，将字符串化为4种标记的状态数组
该题属于统计合格子串数量的题型
判断字串合格的check()
?通常不同题的要求也不同在这里。
?该题比较好写，这里不多赘述。
如果是定长的字串，那就是上面一种滑动窗口的题型了，相对来说好些很多，但这里是不定长。
对于不定长的题目通常一个默认条件就是字串长度的范围在[0, str.length()]之间
但本题给出了最短L和最长R（通常题目也都会给这些条件）
实现思路：
- 设定两个指针，
左指针left 右指针right - 固定
左指针left 让 右指针right不断探索，直到找到合格的字串 - 直到check()到合格的字串，右指针停下，此时有3种状态 (注意这里的check()不考虑长度)
right < L <= R 长度不合格L <= right <= R 长度合格L <= R < right 长度不合格
- 注意，当
右指针right到最后都没check()成功的时候，说明之后再也没各个的字串了，可以直接break掉 - 先思考，如果是理想的状态那就是
left+L 到 left+R都合格 - 但实际是需要根据
右指针right来获得合格串
- 左端点的最小值
int rightMin = max(right, left+L-1); - 右断点的最大值
int rightMax = min(n-1, left+R-1); - 最后判断
rightMin <= rightMax ? true : false 即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main (void) {
int n;
int L, R;
cin >> n >> L >> R;
string s;
cin >> s;
vector<int> kinds(n);
for (int i = 0; i < n; i++) {
if (isupper(s[i])) {
kinds[i] = 0;
} else if (islower(s[i])) {
kinds[i] = 1;
} else if (isdigit(s[i])) {
kinds[i] = 2;
} else {
kinds[i] = 3;
}
}
function<bool(vector<int>)> check = [](const vector<int>& arr) {
int cnt = 0;
for (int num : arr) {
if (num > 0) {
cnt++;
}
}
return cnt >= 3;
};
vector<int> cnt(4);
int ans = 0;
for (int left = 0, right = -1; left < n; left++) {
while (!check(cnt)) {
right++;
if (right < n) {
cnt[kinds[right]]++;
} else {
break;
}
}
if (!check(cnt)) {
break;
}
int rightMin = max(right, left+L-1);
int rightMax = min(n-1, left+R-1);
ans += max(1LL*0, rightMax-rightMin+1);
cnt[kinds[left]]--;
}
cout << ans << endl;
return 0;
}
本题注意要开下long long 不然不能过
虽然我自己把 N=1e5 L=1 R=1e5 串是4种状态循环的长度1e5的串 测了一下
int 和 long long 答案是一样的。
还是有比我上述case更大的答案case？总不见得是平台或是出题人的问题吧？
这里right的操作比较自由，我强定了right必须同步记录状态
比较好写的方式是先记录完再right++则此时合法check()退出循环，那right指向的是合法串的后一个位置
下面计算rightMin也要注意修改写法上的细节
END
|