给定字符串s和整数k，返回字符串s中长度为k的单个子字符串中包含的最大元音字母数

• 暴力枚举：时间复杂度$O(nk)$
• 能否实现$O(1)$计算子串的元音个数？
• 可以实现！假设对于abci，已经计算了abc的原因个数，滑动窗口到bci时，只需要考虑移除a，以及添加i即可

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

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

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

class Solution:def findMaxAverage(self, nums: List[int], k: int) -> float:# 找最大平均值，本质就是找最大加和# maxtotal = 0# total = 0# 错误，直接计算前k个元素加和作为初始化情况maxtotal=total=sum(nums[:k])n = len(nums)# 1.进入窗口,从k索引开始更新窗口for i in range(k, n):# 2.更新答案  3.离开窗口total = total - nums[i-k] + nums[i]maxtotal = max(maxtotal, total)return maxtotal / k

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

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

class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:# k个数平均值大于等于threshold# 相当于k个数加和大于等于k*thresholdsum_threshold = k * threshold  # 门槛sum_val = 0       # 当前子数组加和  res = 0           # 结果，符合要求的子数组个数for i in range(len(arr)):# 1.进入窗口sum_val += arr[i]if i < k - 1: # 窗口大小不足kcontinue  # 先继续加# 2.更新答案if sum_val >= sum_threshold:res += 1# 3.离开上一个元素 sum_val -= arr[i-k+1]return res

一开始写的代码，超时了！

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:# 以下标i为中心，[i-k, i+k]超出[0, n-1]范围直接返回-1# 没超出[0, n-1]范围，计算子数组平均值，其实就是算加和n = len(nums)res = [-1] * n  # 记录结果val = 0  # 当前范围的加和# for i in range(n):# 1.进入窗口if i-k >= 0 and i+k < n:val = sum(nums[i-k:i+k+1])res[i] = val//(2*k+1)# 2.更新答案# 3.(谁？)离开窗口return res

分析：

• 虽然有滑动窗口的思路，但是实现方式导致了效率的问题，比如sum函数调用这一步，重复计算了很多加和，实际滑动窗口是不需要这样算的。
• 去掉离开窗口的元素，加上新加入的元素就可以！
• 这个实现方式完全没有高效利用滑动窗口！

已老实
修改代码如下：

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:# 题意：以下标i为中心，范围是[i-k, i+k]，超出[0, n-1]范围直接返回-1# # 没超出[0, n-1]范围，计算子数组平均值，其实就是算加和n = len(nums)res = [-1] * n  # 记录结果,默认设置为-1# 初始化第一个不为-1的位置，也就是i-k=0,i=k,i+k=2k# 特解：k大于nif k>n:return resval = sum(nums[0: 2*k+1])  # 当前范围的加和res[k] = val // (2*k + 1)# nums[i], 取[i-k, i+k]作为滑动窗口！# 从i=2k+1开始遍历,i+k = n-1结束for i in range(k+1,n-k):# 先处理离开窗口val -= nums[i-k-1]# 进入窗口val += nums[i+k]# 更新答案res[i] = val//(2*k + 1)return res
——————————————————————
执行出错
21 / 40 个通过的测试用例
IndexError: list assignment index out of range~~~^^^res[k] = val // (2*k + 1)
Line 15 in getAverages (Solution.py)^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ret = Solution().getAverages(param_1, param_2)
Line 59 in _driver (Solution.py)_driver()
Line 74 in <module> (Solution.py)
最后执行的输入
添加到测试用例
nums =
[4744,3044,7550,8264,29,9001,8641,5079,9237,4205,5727,8853,688,628,7828,6573,6256,5212,9619,8159,5190,8546,28,648,8114,580,8632,3343,770,1446,8899,9970,2906,843,2404,127,8940,5098,9612,3268,9491,8149,7510,2865,8667,6498,1763,3743,7225,1829,1191,4493,9579,6116,3635,4853,1929,296,8883,5573,9605,6134,963,1896,3274,1782,866,2682,6717,8407,4254,5079,1049,27,9959,3343,6005,2896,1
查看更多
k =
7875

上面代码有个很不严谨的地方，应该是2k>n就直接返回一个值？
改后：

解答错误
39 / 40 个通过的测试用例官方题解
输入
nums =
[2,1]
k =
1添加到测试用例
输出
[-1,1]
预期结果
[-1,-1]

还不对，是2k+1才对，这才是整个窗口大小！

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:# 题意：以下标i为中心，范围是[i-k, i+k]，超出[0, n-1]范围直接返回-1# # 没超出[0, n-1]范围，计算子数组平均值，其实就是算加和n = len(nums)res = [-1] * n  # 记录结果,默认设置为-1# 初始化第一个不为-1的位置，也就是i-k=0,i=k,i+k=2k# 特解：滑动窗口长度大于n时,无需计算任何加和，因为不存在满足要求的子串# 应该直接返回res=[-1-1-1-1-1......]if 2*k+1>n:return resval = sum(nums[0: 2*k+1])  # 当前范围的加和res[k] = val // (2*k + 1)# nums[i], 取[i-k, i+k]作为滑动窗口！# 从i=2k+1开始遍历,i+k = n-1结束for i in range(k+1,n-k):# 先处理离开窗口val -= nums[i-k-1]# 进入窗口val += nums[i+k]# 更新答案res[i] = val//(2*k + 1)return res
——————————————————————————————————
通过

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

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

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

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

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:# 不用真的把白色块涂黑，只需要用滑动窗口，不断更新窗口内白色块数量即可！res = 1000    # 初始化最终结果为足够大的数字white_val = 0  # 当前窗口白块数量black_val = 0  # 当前窗口黑块数量max_b = 0for cur in enumerate(blocks):if cur == 'B':black_val += 1if black_val >= k:return 0if cur == 'W':black_val = 0for i, cur in enumerate(blocks):# 1. 进入窗口if cur == 'W': # 如果当前字符cur时白块，增加一次涂色次数white_val += 1# 如果是黑块，不增加涂色次数，忽略，不用体现在代码中# 如果当前窗口长度（i从0开始索引，i时实际上长度是i+1）还没到k，故i+1<kif i < k - 1:continue # 继续进入窗口，不用 找答案 与 退出窗口# 2. 更新答案res = min(res, white_val)# 3. 退出窗口if blocks[i-k-1] == 'W':white_val -= 1return res

• 第一个错误：一开始我用的是is而不是==，注意is，表示两个对象完全相等，包括内存地址，这里用==才对
• 第二个错误：第一个for循环本意是先看看原字符串是否不用涂就满足要求了！多余！与滑动窗口逻辑完全无关
• 第三个错误：在退出窗口（if blocks[i - k - 1] == ‘W’: white_val -= 1）这一步，只考虑了当前窗口最左边的字符是 ‘W’ 时减少白色块数量，没有考虑到如果最左边的字符是 ‘B’ 时，实际上这个窗口内的黑色块数量增加了，可能会出现连续 k 个黑块的情况，从而应该更新 res 的值。

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:res = len(blocks)  # 初始化最终结果为足够大的数字，这里可以设为字符串长度white_val = 0  # 当前窗口白块数量for i, cur in enumerate(blocks):# 1. 进入窗口if i < k:if cur == 'W':white_val += 1else:# 2. 更新答案res = min(res, white_val)# 退出窗口并进入下一个窗口if blocks[i - k] == 'W':white_val -= 1if cur == 'W':white_val += 1return res
——————————————————————————
解答错误
111 / 122 个通过的测试用例官方题解
输入
blocks =
"BWWWBB"
k =
6添加到测试用例
输出
6
预期结果
3

代码缺陷很容易看到，
添加一行： res = white_val
轻松又通过一个用例！

        for i, cur in enumerate(blocks):# 1. 进入窗口if i < k:  # 窗口长度不足时if cur == 'W':white_val += 1res = white_val
_________________________________
解答错误
113 / 122 个通过的测试用例官方题解
输入
blocks =
"WWBBBWBBBBBWWBWWWB"
k =
16添加到测试用例
输出
7
预期结果
6

继续改，最后一行加了一个res = min(res, white_val)

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:res = len(blocks)    # 初始化最终结果为足够大的数字white_val = 0  # 当前窗口白块数量for i, cur in enumerate(blocks):# 1. 进入窗口if i < k:  # 窗口长度不足时if cur == 'W':white_val += 1res = white_valelse:      # 窗口长度达标# 2. 更新答案res = min(res, white_val)# 退出窗口，并且进入下一个窗口if blocks[i - k] == 'W':white_val -= 1if cur == 'W':white_val += 1# 2. 更新答案res = min(res, white_val)return res
——————————————————————————
解答错误
120 / 122 个通过的测试用例官方题解
输入
blocks =
"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
k =
100添加到测试用例
输出
100
预期结果
0

这个用例，字符串长度等于k，且原本就全是B黑块，一块都不用涂，应该直接返回0，但是由于res初始设置为字符串长度n，而我的代码逻辑没处理这个特例!
所以加两行

• if not ‘W’ in blocks:

• return 0  
  

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:# 不用真的把白色块涂黑，只需要用滑动窗口，不断更新窗口内白色块数量即可！res = len(blocks)    # 初始化最终结果为足够大的数字white_val = 0  # 当前窗口白块数量#black_val = 0  # 当前窗口黑块数量#max_b = 0"""for cur in enumerate(blocks):if cur == 'B':black_val += 1if black_val >= k:return 0if cur == 'W':black_val = 0"""    #n = blocks.lenth()#if k > len(blocks):#   return 0     # if not 'W' in blocks:return 0   for i, cur in enumerate(blocks):# 1. 进入窗口if i < k:  # 窗口长度不足时if cur == 'W':white_val += 1res = white_valelse:      # 窗口长度达标# 2. 更新答案res = min(res, white_val)# 退出窗口，并且进入下一个窗口if blocks[i - k] == 'W':white_val -= 1if cur == 'W':white_val += 1# 2. 更新答案res = min(res, white_val)return res
____________
通过

太艰难了老铁…
看看灵神答案吧

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:ans = cnt_w = blocks[:k].count('W')for in_, out in zip(blocks[k:], blocks):cnt_w += (in_ == 'W') - (out == 'W')ans = min(ans, cnt_w)return ans作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/solutions/1763639/on-hua-dong-chuang-kou-by-endlesscheng-s4fx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

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

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

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

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

• 题目有点绕，慢慢捋顺，目的是找出最多有多少顾客会满意
• 滑动窗口，窗口大小为minutes，窗口内的所有顾客会满意，窗口外，grumpy[i]=0的位置会满意

class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:n = len(customers)     # 分钟数#res = 0                # 最大满意人数val = 0for i in range(n):# 1.初始化窗口：[0, minutes - 1 ]if i < minutes:    val += customers[i]   # 窗口内的所有顾客都满意# 退出窗口if grumpy[i - minutes] == 1:  # 退出窗口的元素会生气val -= customers[i - minutes]   # 退出窗口表示这个时间老板抑制不了生气了，顾客不满意！# 进入窗口，窗口内的都不会生气，顾客都会满意val += customers[i] #res = max(res, val)return val
+———————————————————————————————————————————
只通过5个用例

看了评论区看到别人的思路更清晰些：

• 最多满意客户数量 = 原本就满意的客户 + X时间段内因为控制了情绪而态度反转的最多客户数量 步骤: 1 统计老板不生气时客人数量 2 利用窗口大小为minutes的滑动窗口，找出这个时间段内不满意客户数量的最大值

这个思路i清晰多了！！！
一次过！

class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:n = len(customers)     # 分钟数max_re = 0             # 固定时间态度从差到好反转的人数sum_peo = 0             # 原本就满意的总人数re = 0# 先统计sum_peofor i in range(n):if grumpy[i] == 0:           # 不生气就满意sum_peo += customers[i]  # 满意就算进去# 统计由于老板不生气，态度好转的人# 1.进入窗口if grumpy[i] == 1:  # 统计窗口内态度好转的人数re += customers[i]if i < minutes - 1:     # 窗口长度不到minutes时continue            # 继续加，加到i=minures-1,也就是刚好到窗口长度为止# 跳出continue时，正好是第一个答案# 2.更新答案max_re = max(max_re, re)# 3.退出上一个窗口，（哪一个？i=m-1时，第一次到达窗口长度，此时要退出的是0位置，也就是0=i-(m-1)=i-m+1位置）if grumpy[i- minutes + 1] == 1:re -= customers[i- minutes + 1]return max_re + sum_peo

class Solution:def hasAllCodes(self, s: str, k: int) -> bool:key=set()for i in range(len(s)-k+1):key.add(s[i:i+k:])return len(key)==1<<k

以下是对上述代码知识点重点的简略提炼：