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}
};