《六月集训》（第六天）——滑动窗口

文章目录

• 前言
• 一、练习题目
• 二、算法思路
• 三、源码剖析

前言

        欢迎大家积极在评论区留言发表自己的看法，知无不言，言无不尽，养成每天刷题的习惯，也可以自己发布优质的解题报告，供社区一同鉴赏，吸引一波自己的核心粉丝。
        今天是六月集训第六天：滑动窗口🔥🔥🔥🔥

一、练习题目

        1984. 学生分数的最小差值
        1763. 最长的美好子字符串
        2269. 找到一个数字的 K 美丽值
        995. K 连续位的最小翻转次数

二、class="superseo">算法思路

• 1、1984. 学生分数的最小差值：排序加固定大小的滑动窗口。五月集训有做过🔥
• 2、1763. 最长的美好子字符串：🔥🔥🔥
• 3、2269. 找到一个数字的 K 美丽值：转化为字符串来做，维护k长度的字符串即可。🔥
• 4、995. K 连续位的最小翻转次数：这题的思路有点巧妙，也是看了很多题解，是比较好理解的，用队列来模拟滑动窗口。🔥🔥🔥🔥🔥

三、源码剖析

// 1984. 学生分数的最小差值 
// 写法一（丑陋）
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end()); //(1)
        int n = nums.size(), ans = 1000001;
        int i = 0, j = i + k- 1; //(2)
        while(j < n) {
            if(j - i + 1 > k) i++; //(3)
            ans = min(ans, nums[j] - nums[i]); //(4)
            j++;
        }
        return ans;
    }
};

// 写法二
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 1000001;
        for(int i = 0 ; i < n - k + 1; i++) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

• 1、升序排序;
• 2、定义两个指针：i一开始是指向第一个学生，j一开始指向第k个学生，后面j是不断右移，i,j需要和数组下标对应；
• 3、我们需要维护窗口大小为k，所以如果大于k了我们把i指针左移;
• 4、判断当前窗口中的差值是不是最小的，是的话更新一下，不是的话j，指针继续右移动。
  写法一和写法二思路是一样的都是维护固定窗口

// 1763. 最长的美好子字符串
class Solution {
public:
    string longestNiceSubstring(string s) {
        int maxlen = 0, maxpos = 0;
        for(int i = 0; i < s.length(); ++i) {
            int lower = 0, uper = 0;
            for(int j = i; j < s.length();++j) {
                if(islower(s[j]))  {
                  lower |= 1 << (s[j] - 'a'); //（1）
                } else{
                   uper |= 1 << (s[j] - 'A'); //（2）
                }
                if(lower == uper && j - i + 1 > maxlen) {
                   maxpos = i;
                   maxlen = j - i + 1; 
                } //(3)
            }

        }
        return s.substr(maxpos, maxlen);
    }
};

• 1、总共26个小写字母用这种方式来统计；
• 2、总共26个大写字母用这种方式来统计；
• 3、判断不管大写还是小写是不是一样的值，如果是的话说明是相同字母，长度更新，不断维护最长的字符串即可。

// 2269. 找到一个数字的 K 美丽值
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num); //(1)
        int ans = 0;
        for(int i = 0; i < s.length() - k + 1; ++i) {
            int a = stoi(s.substr(i, k)); //(2)
            if(a != 0 && num % a == 0) {
                ans++;
            }
        }
        return ans;
    }
};

• 1、将数字转换为字符串；
• 2、利用substr函数来维护k长度的子字符串，判断下能不能把原数整除，同时要考虑除数不能为0。

// 995. K 连续位的最小翻转次数
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        queue<int> q; //(1)
        int res = 0;
        for(int i = 0; i  < n; ++i) {
            if(!q.empty() && i >= q.front() + k) {
                q.pop();
            }
            if(nums[i] == (q.size() & 1)) { //(2)
                if(i + k > n) {
                    return -1; //(3)
                }
                q.push(i);
                res++;
            }
        }
        return res;
    }
};

• 1、使用队列来模拟滑动窗口，前面k-1个元素中，以哪些位置起始的子区间有进行了翻转。如果需要翻转就入队，还有一点翻转带来的影响抽象的话其实就是看奇数次还是偶数次。
• 2、这一步其实分情况讨论，如果是0，然后翻转了偶数次，说明还是本身0，需要再次翻转，入队；如果是1，然后翻转了奇数次，会变成0，需要再次翻转。就这两种情况。然后其实还有两种情况，如果是0翻转了奇数次肯定是1，1翻转偶数次还是1，都是1了就不需要考虑了，将这个抽象出来就是nums[i] == (q.size() & 1这样的一个等式。
• 3、考虑剩下的需要翻转k个但是已经超过了最后的大小返回-1。