【六月算法集训 】第六天之滑动窗口

《算法集训传送门》

👉引言

铭记于心🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉

💖
❄️我们的算法之路❄️💖

众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
               ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

今日主题：滑动窗口

👉⭐️第一题💎

✨题目

      1984. 学生分数的最小差值

✨思路：

由题说明如果要得到 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 ，那么这k个数值必然是连续的（前提是对数组已经排好序的情况下），然后用一个长度为k的窗口遍历取两端差值的最小即可

✨代码：

classSolution{public:intminimumDifference(vector<int>& nums,int k){sort(nums.begin(), nums.end());int min =1000000000;if(nums.size()==1)return0;for(int i =0; i < nums.size(); i++){int i2 = i + k -1;if(i2==nums.size())break;int t = nums[i2]- nums[i];if(t<min)min = t;}return min;}};

👉⭐️第二题💎💎

✨题目

      1763. 最长的美好子字符串

第一种是最简单的暴力解，由于数据范围，遍历所有子串，找出符合规则的一个返回；第二种则是给定一个滑动窗口，维护其中的字符种数，大小字符出现的次数等信息，最长的完美字符串一定出现在某个窗口中

✨代码：

classSolution{public:boolcheck(string& str){
    set<char>Check;for(int i =0; i < str.size(); i++){
        Check.insert(str[i]);}for(char t:Check){if((Check.find(toupper(t)))==Check.end()||(Check.find(tolower(t))== Check.end()))returnfalse;}returntrue;}
string longestNiceSubstring(string s){int leMax =0;
    vector<string> ans;for(int i =0; i < s.size(); i++){for(int j = i; j < s.size(); j++){
            string tem(s, i, j - i +1);if(check(tem)){
                leMax =max((int)tem.size(), leMax);
                ans.push_back(tem);}}}for(string t : ans){if(leMax == t.size())return t;}return"";}};

class Solution {
public:
    string longestNiceSubstring(string s){int maxPos =0, maxLen =0;auto check =[&](int typeNum){
            vector<int>lowerCnt(26);
            vector<int>upperCnt(26);int cnt =0;for(int l =0, r =0, total =0; r < s.size();++r){int idx =tolower(s[r])-'a';if(islower(s[r])){++lowerCnt[idx];if(lowerCnt[idx]==1&& upperCnt[idx]>0){++cnt;}}else{++upperCnt[idx];if(upperCnt[idx]==1&& lowerCnt[idx]>0){++cnt;}}
                total +=(lowerCnt[idx]+ upperCnt[idx])==1?1:0;while(total > typeNum){
                    idx =tolower(s[l])-'a';
                    total -=(lowerCnt[idx]+ upperCnt[idx])==1?1:0;if(islower(s[l])){--lowerCnt[idx];if(lowerCnt[idx]==0&& upperCnt[idx]>0){--cnt;}}else{--upperCnt[idx];if(upperCnt[idx]==0&& lowerCnt[idx]>0){--cnt;}}++l;}if(cnt == typeNum && r - l +1> maxLen){
                    maxPos = l;
                    maxLen = r - l +1;}}};int mask =0;for(char& ch : s){
            mask |=1<<(tolower(ch)-'a');}int types =__builtin_popcount(mask);for(int i =1; i <= types;++i){check(i);}return s.substr(maxPos, maxLen);}};

👉⭐️第三题💎💎

✨题目

      2269. 找到一个数字的 K 美丽值

✨思路：

其实这道题就是个字符串与整型值相互转化的问题，先将num转化为字符串，维护一个长度为k的窗口，依次取出其中的子串，然后转化为数字看是否能够整除num

✨代码：

classSolution{public:intdivisorSubstrings(int num,int k){
    stringstream ss;
    ss << num;
    string tar;
    ss >> tar;int sum =0;for(int i =0; i < tar.size(); i++){
        string t(tar, i, k);if(t.size()!= k)break;int tem=atoi(t.c_str());if(tem ==0)continue;if(!(num % tem))sum++;}return sum;}};

👉⭐️第四题💎💎💎💎

✨题目

      995. K 连续位的最小翻转次数

✨思路：

后面区间的翻转，不会影响前面的元素。因此可以使用贪心策略，从左到右遍历，遇到每个 0 都把 它以及后面的 K-1K−1 个元素进行翻转 ，A[i] 翻转偶数次的结果是 A[i]A[i]；翻转奇数次的结果是 A[i] ^ 1

✨代码：

classSolution{public:intminKBitFlips(vector<int>& A,int K){int N = A.size();
        queue<int> que;int res =0;for(int i =0; i < N;++i){if(!que.empty()&& i >= que.front()+ K){
                que.pop();}if(que.size()%2== A[i]){if(i + K > N){return-1;}
                que.push(i);
                res ++;}}return res;}};

⭐️总结⭐️

滑动窗口也叫作尺取法，其本质就是维护数组中一个长度为k的子数组，以及其中的一些信息，最后一题其实就是不那么容易想出来，但是理解了也很容易弄明白

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！