定长滑动窗口（基础）

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

class Solution:def maxVowels(self, s: str, k: int) -> int:ans = 0     # 记录每次滑动窗口元音字母个数最大的答案tmp = 0     # 滑动窗口内的元音字母个数left = 0    # 左指针table = ["a", "e", "i", "o", "u"]for right, x in enumerate(s):if x in table:tmp += 1# 这里不用while判断是因为每一轮我们都要判断一次if right - left + 1 > k:    if s[left] in table:tmp -= 1left += 1ans = max(ans, tmp)return ans

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

class Solution:def findMaxAverage(self, nums: List[int], k: int) -> float:left = 0ans = -inf  # 记录滑动窗口最大答案tmp = 0  # 每次滑动窗口内答案for right, x in enumerate(nums):tmp += xif right - left + 1 > k:  # 长度大于k，移动左指针tmp -= nums[left]left += 1if right - left + 1 == k:  # 当滑动窗口长度为k时才记录答案ans = max(ans, tmp / k)return ans

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例 1：

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:left = 0ans = 0  # 记录子数组个数tmp = 0  # 记录滑动窗口内总和for right, x in enumerate(arr):tmp += x  # 元素进窗口if right - left + 1 > k:  # 元素出窗口tmp -= arr[left]left += 1if right - left + 1 == k and tmp / k >= threshold:ans += 1  # 记录答案return ans

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

• 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0
输出：[100000]
解释：
- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000
输出：[-1]
解释：
- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:avg = [-1] * len(nums)  # 答案数组全部初始化为-1left = 0tmp = 0  # 记录窗口内元素总和for right, x in enumerate(nums):tmp += x  # 元素进入窗口if right - left + 1 > k * 2 + 1:  # 元素离开窗口tmp -= nums[left]left += 1if right - left + 1 == k * 2 + 1:# (right+left)//2表示左指针和右指针中间的下标，在此下标记录答案avg[(right + left) // 2] = tmp // (k * 2 + 1)return avg

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:left = 0  # 左指针opt = 0  # 记录滑动窗口内的总共操作次数ans = inf  # 记录最小操作次数for right, x in enumerate(blocks):if x == "W":  # 窗口内的操作次数opt += 1if right - left + 1 > k:if blocks[left] == "W":opt -= 1left += 1  # 元素离开窗口if right - left + 1 == k:  # 记录答案ans = min(opt, ans)return ans

给你一个整数数组 nums 和两个正整数 m 和 k 。

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

子数组指的是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。

示例 2：

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
输出：23
解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。

示例 3：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。

class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:from collections import defaultdictwin = defaultdict(int)  # 存放滑动窗口内的元素出现次数left = 0tmp = 0  # 记录滑动窗口内元素总和ans = 0  # 记录最大总和for right, x in enumerate(nums):win[x] += 1  # 元素出现次数加1tmp += x  # 总和加xif right - left + 1 > k:  # 元素个数超过k，移除首元素tmp -= nums[left]win[nums[left]] -= 1if win[nums[left]] == 0:del win[nums[left]]  # 一定要删除，否则滑动窗口的长度不会变left += 1if len(win) >= m:  # 记录答案ans = max(ans, tmp)return ans

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
• 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:from collections import defaultdictwin = defaultdict(int)  # 存放滑动窗口内的元素出现次数left = 0tmp = 0  # 记录滑动窗口内元素总和ans = 0  # 记录最大总和for right, x in enumerate(nums):win[x] += 1  # 元素出现次数加1tmp += x  # 总和加x# 保证元素个数不超过k且所有元素互不相同while right - left + 1 > k or win[x] > 1:tmp -= nums[left]win[nums[left]] -= 1if win[nums[left]] == 0:del win[nums[left]]  # 一定要删除，否则滑动窗口的长度不会变left += 1if right - left + 1 == k:  # 记录答案ans = max(ans, tmp)return ans

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。 

示例 5：

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202

class Solution:def maxScore(self, cardPoints: List[int], k: int) -> int:# 求滑动窗口长度为len(cardPoints)-k，点数之和最小l = len(cardPoints) - k  # 记录答案时滑窗长度ans = inf  # 滑窗内最小总和left = 0tmp = 0  # 滑窗总和for right, x in enumerate(cardPoints):tmp += xif right - left + 1 > l:tmp -= cardPoints[left]left += 1if right - left + 1 == l:ans = min(ans, tmp)return sum(cardPoints) - ans

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:# 不使用秘密技巧时的满意的顾客总和sum_ = sum([customers[i] for i in range(len(customers)) if grumpy[i] == 0])ans = 0  # 记录使用秘密技巧时最多让多少顾客回心转意tmp = 0  # 滑动窗口内多少顾客回心转意left = 0for right, x in enumerate(customers):minutes -= 1  # 由于必须是连续minutes不生气，所以每次都要先-1if grumpy[right] == 1:tmp += x  # 记录答案while minutes < 0:if grumpy[left] == 1:tmp -= customers[left]left += 1  # 元素离开窗口minutes += 1ans = max(ans, tmp)return sum_ + ans

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

• 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
• 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
• 如果 k == 0 ，将第 i 个数字用 0 替换。

由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

示例 1：

输入：code = [5,7,1,4], k = 3
输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字之和替换。解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。

示例 2：

输入：code = [1,2,3,4], k = 0
输出：[0,0,0,0]
解释：当 k 为 0 时，所有数字都被 0 替换。

示例 3：

输入：code = [2,4,9,3], k = -2
输出：[12,5,6,13]
解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。如果 k 是负数，那么和为 之前 的数字。

class Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)if k == 0:return [0] * ncode = code * 3  # 将数组前后拼接与它相同的数组left = 0sum_ = 0  # 记录滑动窗口的总和ans = [0] * len(code)  # 答案数组for right, x in enumerate(code):sum_ += xif right - left + 1 > abs(k):  # 一定要加绝对值，k有可能为负数sum_ -= code[left]left += 1if k > 0:if left > 0:  # 防止越界ans[left - 1] = sum_else:if right < len(code) - 1:  # 避免越界ans[right + 1] = sum_return ans[n : n * 2]  # 取需要的答案