【基础算法训练】——滑动窗口

- 💓前言
- 💓知识铺垫
- 💓第一题 1984. 学生分数的最小差值
- - 💒题目描述
  - 🌟解题报告
  - 🌻参考代码(C++版本)
- 💓第二题 1876. 长度为三且各字符不同的子字符串
- - 💒题目描述
  - 🌟解题报告
  - 🌻参考代码(C++版本)
- 💓第三题 1052. 爱生气的书店老板
- - 💒题目描述
  - 🌟解题报告
  - 🌻参考代码(C++版本)
- 💓第四题 1839. 所有元音按顺序排布的最长子字符串
- - 💒题目描述
  - 🌟解题报告
  - 🌻参考代码(C++版本)
- 💓总结

💓前言

每日算法练习，千锤百炼，静待花开。

现在的单片机是会持续更的，因为我要靠它去捣腾暑假实习的事儿：十四天学会51单片机；
Leetcode的专栏会持续更，因为在跟着英雄哥做知识星球的事儿：在lc被欺负的这些年；
对英雄哥的知识星球有兴趣的可以看看他这篇文章喔： 英雄算法联盟 | 31天让你的算法与众不同

至于现在这专栏了，是我4月12号的想法，这个专栏只会记录全部是每日的算法题：知识星球每天的习题，以及在咱高校算法学习社区中，泡泡和p佬普及组和提高组的题目，一般是当天写当天更吧。我一般会先写星球上的题，因为泡泡他俩的题有点难，得晚点补上

💓知识铺垫

对于滑动窗口，在分类上，有固定的窗口，也有非固定的窗口，一般是基于数组进行求解。

对于一个数组中两个相邻窗口，会有一大部分重叠的部分，这部分重叠的内容是不需要重复计算的，所以我们可以通过相邻的窗口进行数据的延续使用。

上面两个是长度为4，彼此相邻的窗口，也可以看到，其实大部分数据是相同的，
只是上一个窗口比下一个窗口左端多出一个数据，下一个比上一个右端多出一个数据了。

橙色的点是状态切换之后减少的数据，黄色的点是增加的数据，所以在下一次状态变换时，不用动不变的值，直接修改这两个变化的值就好。
其实我感觉滑动窗口和双指针关系蛮大的…

💓第一题 1984. 学生分数的最小差值

💒题目描述

原题传送门

🌟解题报告

通过样例2，小伙伴们应该也能感觉到，排序以后更好处理，那咱就先排序，模拟滑动的过程吧。
① 先确定一个题目要求范围内的窗口： int ans = nums[k-1] - nums[0];
② 更新窗口的首尾元素，模拟窗口滑动的过程

🌻参考代码(C++版本)

class Solution {
public:int minimumDifference(vector<int>& nums, int k) {int n = nums.size();if(n == 1) return 0;sort(nums.begin(),nums.end());int ans = nums[k-1] - nums[0];for(int i = k; i < n;i++)//通过循环遍历，模拟滑动的过程ans = min(nums[i] - nums[i-k+1],ans);return ans;}
};

💓第二题 1876. 长度为三且各字符不同的子字符串

💒题目描述

原题传送门

🌟解题报告

这种数据范围呢，咋折腾都可以了。解法一就是常规的模拟，比较。
解法二回到咱们今天练习的滑动窗口上，窗口的长度就是题目要求中的3。

🌻参考代码(C++版本)

解法一——想法不要太多，反手直接暴力

class Solution {
public:int countGoodSubstrings(string s) {int ans = 0;int n = s.size();for (int i = 0; i < n - 2; ++i){if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) ans ++;}return ans;}
};

解法二——可爱滑动窗口

class Solution {
public:int countGoodSubstrings(string s) {int l = 0,r = 2;int n = s.size();int i,j,cnt = 0;bool flag;//开始模拟滑动的过程while(r < n){flag = true;//标记当前处理的窗口是否满足要求for(i = l;i < l + 2;i++)for(j = i+1;j <= l + 2;j++)if(s[i] == s[j]) {flag = false;break;}if(flag) cnt++;l ++,r++;//这种固定窗口长度的了，就得一起滑动了}return cnt;}
};

💓第三题 1052. 爱生气的书店老板

💒题目描述

原题传送门

🌟解题报告

这个老板挺个性的呀

先统计一个基础的值吧，在老板不使用这个特殊技巧的时候，把这些满意的客户的数量统计出来。
把使用这个秘密技巧的时候minutes作为滑动窗口的长度，去原数组中遍历，找到因为使用技巧之后，能够获得的最大的满意用户的数量。
注意对第一个窗口的初始化处理。

🌻参考代码(C++版本)

class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int m = customers.size();int ans = 0;//统计满意的客户的人数//统计常规情况下，老板不生气的时候，满意的客户的人数for(int i = 0; i < m;i++)if(!grumpy[i]) ans += customers[i];//现在统计老板使用这个技巧了，原本不满意的，在这个时间范围内满意了int tmp = 0;//第一个窗口的情况for(int i =0; i < minutes;i++)if(grumpy[i] == 1) tmp += customers[i];//使用技巧之后新增加的用户的数量int addNum = tmp;//滑动窗口具体滑动的过程了//在技巧时间内，去挽救那些原本因为生气而不满意的客户for(int i = minutes; i < m;i++){if(grumpy[i] == 1) tmp += customers[i];if(grumpy[i-minutes] == 1) tmp -= customers[i-minutes];//统计滑动期间的最大值addNum = max(addNum,tmp);}return ans + addNum;}
};

💓第四题 1839. 所有元音按顺序排布的最长子字符串

💒题目描述

原题传送门

🌟解题报告

看到字符串的东西了，心里的想法就不要离开哈希表太远了。
可以用数组模拟哈希表，比如a[3]的数值是5，就可以表示索引是3的字符有5个。
当然，也可以直接使用C++为咱们造好的轮子。

关于这个容器，是有好几个了，因为确实也比较常用，我抽个时间啃一下源码，把捋清楚。

元素按字典序排列需要比较新元素和窗口中元素的字典序，
5个元音字母必须全部出现可以使用一个set来统计窗口中字符的种类，种类满足五个了，就是符合要求了。
至于滑动窗口的逻辑了，就是判断当前是否还是处于升序。
倘若还是升序并且右指针没有达到端点，就滑动右指针去拓展这个窗口
倘若不是升序了，就得调整左指针了。

🌻参考代码(C++版本)

class Solution {
public:int longestBeautifulSubstring(string word) {int n = word.size();if(n < 5) return 0;//开一个存字符类型的哈希表unordered_set<char> st;int ans = 0;//统计最长的字符串数量st.insert(word[0]);char tmp = word[0];int l = 0,r = 1;while(r < n){//不再满足aeiou的升序if(tmp > word[r]){//倘若满足要求，进行统计if(st.size() == 5) ans = max(ans,r-l);//无论如何，都清空当前这轮哈希表st.clear();//移动左端口，进行下一次滑动l = r;}tmp = word[r];st.insert(word[r]);//滑动右端口r ++;}//如果最后到右端点都是aeiou的升序// cout << "此时的r = " << r <<",l=" << l<<endl;if(st.size() == 5) ans = max(ans,r-l);return ans;}
};