哪里有做网站排名优化,网站建设简介淄博,网站建设评比办法,湖北企业网站建设公司5. 2379.得到k个黑块的最少涂色次数(简单)
2379. 得到 K 个黑块的最少涂色次数 - 力扣#xff08;LeetCode#xff09;
思想
1.返回至少出现 一次 连续 k 个黑色块的 最少 操作次数 2.还是定长k#xff0c;统计量就是把白色变成黑色的操作次数#xff0c;无需记录当前有…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(vectorint nums, int m, int k) {long long res 0, sum 0;mapint, 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-k0要单独判断先返回答案
代码
c:
class Solution {
public:int maxScore(vectorint 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; //窗口长度不为0res!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(vectorint customers, vectorint 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}
};
