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

《算法集训传送门》   👉引言

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

---

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

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

---

今日主题：滑动窗口

---

 👉⭐️第一题💎    ✨题目

      1984. 学生分数的最小差值

   ✨思路：

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

   ✨代码：

class Solution {
public:
 int minimumDifference(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
	int min = 1000000000;
	if (nums.size() == 1)return 0;
	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. 最长的美好子字符串

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

   ✨代码：

class Solution {
public:
bool check(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()))return false;
	}return true;
}
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

   ✨代码：

class Solution {
public:
   int divisorSubstrings(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

   ✨代码：

class Solution {
public:
    int minKBitFlips(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的子数组，以及其中的一些信息，最后一题其实就是不那么容易想出来，但是理解了也很容易弄明白

---

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