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

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

算法集训传送门》   👉引言

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

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

   众所周知,作为一名合格的程序员,算法 能力 是不可获缺的,并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
               ☀️🌟短短几行代码,凝聚无数前人智慧;一个普通循环,即是解题之眼🌟☀️
   💝二分,💝贪心,💝并查集,💝二叉树,💝图论,💝深度优先搜索(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的子数组,以及其中的一些信息,最后一题其实就是不那么容易想出来,但是理解了也很容易弄明白


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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1329688.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-12
下一篇 2022-06-12

发表评论

登录后才能评论

评论列表(0条)

保存