网站设计建设公司服务商,温州建设工程招聘信息网站,网站导航这么做,昆明网站写在前面#xff1a;全部题都源于力扣 讲解题目一#xff1a;最小覆盖子串题目二#xff1a;字符串排列题目三#xff1a;找所有字母异位词题目四#xff1a;无重复字符的最长子串题目五#xff1a;滑动窗口的最大值 讲解
滑动窗口算法技巧主要用来解决子数组问题#… 写在前面全部题都源于力扣 讲解题目一最小覆盖子串题目二字符串排列题目三找所有字母异位词题目四无重复字符的最长子串题目五滑动窗口的最大值 讲解
滑动窗口算法技巧主要用来解决子数组问题比如让你寻找符合某个条件的最长/最短子数组。 如果用暴力解的话你需要嵌套 for 循环这样穷举所有子数组时间复杂度是O(n2)
for(int i 0; i nums.size(); i ){for(int j i; j nums.size(); j ){//维护一个nums[i,j]的子数组}
}滑动窗口其实也并不难就是维护一个窗口不断滑动不断更新答案大致逻辑
int left 0, right 0;while (right nums.size()) {// 增大窗口window.addLast(nums[right]);right;while (window needs shrink) {// 缩小窗口window.removeFirst(nums[left]);left;}
}由于这套逻辑left和right都不会回退所以滑动窗口的时间复杂度是O(n)
没了讲解到此结束 只学讲解是没有办法乱杀滴接下来就靠着这个模板魔改解决hard题吧
题目一最小覆盖子串
力扣难度hard-传送门 滑动窗口的思路是这样的
在字符串 S 中使用双指针中的左右指针技巧初始化 left right 0把索引左闭右开区间 [left, right) 称为一个「窗口」。 问为什么设计为左闭右开区间 答因为这样初始化 left right 0 时区间 [0, 0) 中没有元素但只要让 right 向右移动扩大一位区间 [0, 1) 就包含一个元素 0 了。如果设置为两端都开的区间那么让 right 向右移动一位后开区间 (0,1) 仍然没有元素如果设置为两端都闭的区间那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。 先不断地增加 right 指针扩大窗口 [left, right)直到窗口中的字符串符合要求包含了 t 中的所有字符。此时我们停止增加 right转而不断增加 left 指针缩小窗口 [left, right)直到窗口中的字符串不再符合要求不包含 t 中的所有字符了。同时每次增加 left我们都要更新一轮结果重复第 2 和第 3 步直到 right 到达字符串 s 的尽头。
talk is cheap,show me the code
首先需要window和need两个哈希表用来记录窗口中已有的字符和需要凑齐的字符
// 记录 window 中的字符出现次数
unordered_mapchar, int window;
// 记录所需的字符出现次数
unordered_mapchar, int need;
for(char c : t) need[c] ;现在开始套模板只需要思考以下几个问题 什么时候应该移动 right 扩大窗口窗口加入字符时应该更新哪些数据 答只要窗口内没有满足t字符都有的话就应该继续扩大窗口窗口加入字符时需要更新窗口大小(window)必备字符个数(window[c])已满条件的字符数(valid)。 while(right s.size()){char c s[right];//加入滑动窗口的值right ;//窗口变大//新加入的值是否需要,需要的话if(need(c)){window[c];//已有的必备值加加if(window[c] need[c]) valid;//如果某个字符在此窗口已经满足条件valid}
}什么时候窗口应该暂停扩大开始移动 left 缩小窗口从窗口移出字符时应该更新哪些数据 答当 valid 满足 need 时应该收缩窗口应该在收紧窗口的时候更新最终数据更新窗口大小更新valid(移除元素了这里只可能减)window[字符]数量另外更新最小覆盖子串的起始位置。因为答案一定是在缩窗口的时候出现的所以应该在这里更新len和start // 判断左侧窗口是否要收缩while (valid need.size()) {// 在这里更新最小覆盖子串if (right - left len) {start left;len right - left;}// d 是将移出窗口的字符char d s[left];// 缩小窗口left;// 进行窗口内数据的一系列更新if (need.count(d)) {if (window[d] need[d])valid--;window[d]--;}我们要的结果应该在扩大窗口时还是缩小窗口时进行更新 答一定是在缩小的时候 整体代码
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar, int need, window;for (char c : t) {need[c];}int left 0, right 0;// 记录window中的字符满足need条件的字符个数int valid 0;// 记录最小覆盖子串的起始索引及长度int start 0, len INT_MAX;while (right s.size()) {// c 是将移入窗口的字符char c s[right];// 扩大窗口right;// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c])valid;}// 判断左侧窗口是否要收缩// 用while一种缩到不能再缩while (valid need.size()) {// 在这里更新最小覆盖子串// 必须先将len记录下来再更新窗口大小// 只有这样才能记录每一次合法len然后更新if (right - left len) {start left;len right - left;}// d 是将移出窗口的字符char d s[left];// 缩小窗口left;// 进行窗口内数据的一系列更新if (need.count(d)) {if (window[d] need[d])valid--;window[d]--;}}}// 返回最小覆盖子串// 等于INT_MAX的话返回的是不是 return len INT_MAX ? : s.substr(start, len);}
};题目二字符串排列
力扣567 mid难度s1是可以包含重复字符的哦 是明显的滑动窗口算法相当给你一个 S 和一个 T请问你 S 中是否存在一个子串包含 T 中所有字符且不包含其他字符 基本和题目一是一样的只有几个地方需要注意
本题移动 left 缩小窗口的时机是窗口大小大于 t.length() 时因为排列嘛显然长度应该是一样的。当发现 valid need.size() 时就说明窗口中就是一个合法的排列所以立即返回 true。至于如何处理窗口的扩大和缩小和最小覆盖子串完全相同。
完整代码
class Solution {
public:bool checkInclusion(string t, string s) {unordered_mapchar, int need, window;for (char c : t) need[c];int left 0, right 0, valid 0;while (right s.size()) {char c s[right];if (need.count(c)) {window[c];if (window[c] need[c]) valid;}while (right - left t.size()) { // 严格大于以便准确控制窗口大小char d s[left];if (need.count(d)) {if (window[d] need[d]) valid--;window[d]--;}}// valid need.size()if (right - left t.size() valid need.size()) // 确保窗口大小严格等于t的长度return true;}return false;}
};
题目三找所有字母异位词
力扣438 异位词就是排列啊搞了个高端的说法也糊弄不了我们这些绝顶聪明的娃 直接上代码
class Solution {
public:vectorint findAnagrams(string s, string t) {unordered_mapchar, int need, window;for (char c : t) {need[c];}int left 0, right 0;int valid 0;// 记录结果vectorint res;while (right s.size()) {char c s[right];right;// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c]) {valid;}}// 判断左侧窗口是否要收缩while (right - left t.size()) {char d s[left];left;// 进行窗口内数据的一系列更新if (need.count(d)) {if (window[d] need[d]) {valid--;}window[d]--;}}if(right - left t.size() valid need.size()){res.push_back(left);}}return res;}
};
题目四无重复字符的最长子串
力扣3. 这题在双指针里面用双指针解决过了 如果用滑动窗口的话也很容易 窗口缩的条件就是window[c] 1说明有重复了 和双指针思路一模一样 双指针维护[ji]数组
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
int a[N];
int s[N];
int main(){int n;int r 0;cin n;for(int i 0, j 0; i n; i ){cin a[i];s[a[i]] ;//记录个数while(s[a[i]] 1){-- s[a[j ]];}r max(r, i - j 1);}cout r;
}滑动窗口
class Solution {
public:int lengthOfLongestSubstring(string s) {int left 0;int right 0;int r 0;unordered_mapchar, int window;while(right s.size()){char c s[right];right;window[c];while(window[c] 1){char d s[left];window[d]--;left;}r max(r, right - left);}return r;}
};题目五滑动窗口的最大值
经典滑动窗口力扣239 又名单调队列的实现
和题目1~4不一样这题滑动窗口大小固定每一次的移动也固定难点在于求最大值
这里实现队列要有poppush操作因为题目的特殊性再加个返回最大值的max操作 我们需要逐步实现这三个API
push push 方法依然在队尾添加元素但是要把前面比自己小的元素都删掉
void push(int n) {// 将前面小于自己的元素都删除while (!maxq.empty() maxq.back() n) {maxq.pop_back();}maxq.push_back(n);
}max 如果每个元素被加入时都这样操作最终单调队列中的元素大小就会保持一个单调递减的顺序因此我们的 max 方法可以可以这样写
int max() {// 队头的元素肯定是最大的return maxq.front();}pop pop 方法在队头删除元素 n
void pop(int n) {if (n maxq.front()) {maxq.pop_front();}
}所以综合代码
class slidingQueue{
private:dequeint maxq;
public:void push(int n){while(!maxq.empty() n maxq.back()) maxq.pop_back();maxq.push_back(n);}int max(){return maxq.front();}void pop(int n){if(!maxq.empty() maxq.front() n) maxq.pop_front();}
};
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {slidingQueue window;vectorint res;for(int i 0; i nums.size(); i ){if(i k - 1){window.push(nums[i]);}else{window.push(nums[i]);res.push_back(window.max());window.pop(nums[i - k 1]);}}return res;}
};
