每日算法刷题Day8 5.15:leetcode滑动窗口4道题，用时1h
5. 2379.得到k个黑块的最少涂色次数(简单)
2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）
思想
1.返回至少出现 一次 连续 k 个黑色块的 最少 操作次数
2.还是定长k，统计量就是把白色变成黑色的操作次数，无需记录当前有多少个黑色
，应为维护定长k，一定是k个黑色块
代码
c++:
class Solution {
public:int minimumRecolors(string blocks, int k) {int res = 1e9, cnt = 0;for (int i = 0; i < blocks.size(); ++i) {if (blocks[i] == 'W')cnt++;if (i < k - 1)continue;res = min(res, cnt);if (blocks[i - k + 1] == 'W')cnt--;}return res;}
};
6. 2841.几乎唯一子数组的最大和(中等)
2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）
思想
1.返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0
2.如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
3.本题与前几题区别在于统计量要记录子数组互补相同元素的个数，及每个元素出现的次数(为了删除元素)，所以需要一个哈希表map来维护
代码
c++:
class Solution {
public:long long maxSum(vector<int>& nums, int m, int k) {long long res = 0, sum = 0;map<int, int> mp;for (int i = 0; i < nums.size(); ++i) {sum += (long long)nums[i];mp[nums[i]]++;if (i < k - 1)continue;if (mp.size() >= m)res = max(res, sum);sum -= (long long)nums[i - k + 1];mp[nums[i - k + 1]]--;if (mp[nums[i - k + 1]] <= 0)mp.erase(nums[i - k + 1]);}return res;}
};
注意:
1.erase()方法，不是remove
python:
class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:res, sum = 0, 0cnt = defaultdict(int)for i in range(len(nums)):sum += nums[i]cnt[nums[i]] += 1if i < k - 1:continueif len(cnt) >= m:res = max(res, sum)sum -= nums[i - k + 1]cnt[nums[i - k + 1]] -= 1if cnt[nums[i - k + 1]] == 0:del cnt[nums[i - k + 1]]return res注意:
1.用defaultdict(int),可以自动为不存在的键生成默认值，避免手动判断和初始化,类似于c++的map,而dict{}不行
2.用del删除元素
7. 1423.可获得的最大点数(中等)
1423. 可获得的最大点数 - 力扣（LeetCode）
思想
1.每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌,请你返回可以获得的最大点数。
2.本题逆向思维，求n-k长度的最小值即可，但是要注意,滑动窗口的一个前提条件是窗口大小>0,所以n-k=0要单独判断，先返回答案
代码
c++:
class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {int n = cardPoints.size();long long totalSum = 0;for (int x : cardPoints)totalSum += (long long)x;long long res = 1e18, sum = 0;int len = n - k;if (len == 0)return totalSum; //窗口长度为0for (int i = 0; i < n; ++i) {sum += (long long)cardPoints[i];if (i < len - 1)continue;res = min(res, sum);sum -= (long long)cardPoints[i - len + 1];}return totalSum - res; //窗口长度不为0，res!=1e18}
};
8. 1052.爱生气的书店老板(中等)
1052. 爱生气的书店老板 - 力扣（LeetCode）
思想
1.当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
2.题目要求感到满意的用户数量，可以依据老板生气的0/1划分为两部分sum0,sum1。sum0为老板本来就是0的总人数，与minutes无关，可以一开始直接求出。sum1为老板在minutes内从1变成0的总人数，所以为定长滑动窗口，统计量的判断条件就是生气1，统计量就是sum1。
代码
class Solution {
public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int n = customers.size();int res = 0, sum0 = 0, sum1 = 0;for (int i = 0; i < n; ++i) {if (grumpy[i] == 0) {sum0 += customers[i];}}for (int i = 0; i < n; ++i) {if (grumpy[i] == 1)sum1 += customers[i];if (i < minutes - 1)continue;res = max(res, sum1);if (grumpy[i - minutes + 1] == 1)sum1 -= customers[i - minutes + 1];}return sum0 + res; // 加res，而不是sum1}
};