Leetcode刷题-滑动窗口
1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
1456
class Solution:
def maxVowels(self, s: str, k: int) -> int:
res = 0
now = 0
p = ['a','e','i','o','u']
for i in range(len(s)):
if s[i] in p:
now += 1
if i < k - 1:
continue
res = max(res,now)
if s[i - k + 1] in p:
now -= 1
return res
643
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
res = -99999
now = 0
for i in range(len(nums)):
now += nums[i]/k
if i < k - 1:
continue
res = max(now,res)
now -= nums[i - k + 1]/k
return res
1343
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
threshold *= k
res = 0
now = 0
for i in range(len(arr)):
now += arr[i]
if i < k - 1:
continue
if now >= threshold:
res += 1
now -= arr[i - k + 1]
return res
2090
思路：将题目转化为求数组中2*k+1个连续数字的平均值。
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
res = []
now = 0
f = k
k = 2*k + 1
for i in range(len(nums)):
res.append(-1)
for i in range(len(nums)):
now += nums[i]
if i < k - 1:
continue
# print(now)
r = now // k
res[i - f] = r
now -= nums[i - k + 1]
return res
2379
class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
res = k
now = 0
for i in range(len(blocks)):
if blocks[i] == 'W':
now += 1
if i < k - 1:
continue
res = min(res, now)
if blocks[i - k + 1] == 'W':
now -= 1
return res
1052
思路：先统计在不使用情绪控制技巧的情况下能让多少顾客满意，然后在此基础上使用情绪控制技巧。这时问题已经转化成了找到长度为minutes的连续子数组中 customers[i] > 0 and grumpy[i] == 1 的customer数量，也就是在情绪控制技巧时间持续范围内最大能够让多少本该不满意的顾客满意，也就是使用滑动窗口法找出不满意顾客最多的那个连续子数组。
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
res = 0
now = 0
for i in range(len(customers)):
if customers[i] > 0 and grumpy[i] == 0:
res += customers[i]
now = res
for i in range(len(customers)):
if customers[i] > 0 and grumpy[i] == 1:
now += customers[i]
if i < minutes - 1:
continue
res = max(now, res)
if customers[i - minutes + 1] > 0 and grumpy[i - minutes + 1] == 1:
now -= customers[i - minutes + 1]
return res
1461
思路：使用定长滑动窗口找出所有的长度为k的二进制子串，而长度为k的子串有 2k 2^{k}2k个，所以我们只要使用集合将一个字符串的所有长度为k的子串的数量计算出来，再与2k 2^{k}2k对比就可以得到答案了。（字符串长度小于2k 2^{k}2k的可以直接判False，因为长度小于2k 2^{k}2k的字符串不能产生2k 2^{k}2k个子串）
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < 2**k:
return False
p = set()
for i in range(k - 1, len(s)):
p.add(s[i - k + 1: i + 1])
print(len(p))
if len(p) < 2**k:
return False
else:
return True
2841
思路：所有元素每次移入移出窗口都判断有没有在除了该位置本身的其他位置出现过，移入时如果没出现过那么 l += 1，移出时如果没出现过则 l -= 1，每次比较l和m的大小，l大于等于m时此时的和与目前记录的和做比较，取最大值。
class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
res = 0
l = 1
now = 0
p1 = 0 #窗口的第一个位置
#对nums长度为1的情况进行特殊处理
if len(nums) <= 1:
return nums[0]
for i in range(0,len(nums)):
#对 i=0 的情况进行特殊处理
if nums[i] not in nums[p1 : i] and i != p1:
l += 1
now += nums[i]
if i < k - 1:
continue
if l >= m:
res = max(res, now)
p1 = i - k + 2
#对 k=1 的情况进行特殊处理
if nums[i - k + 1] not in nums[p1 : i + 1] and k > 1:
l -= 1
now -= nums[i - k + 1]
return res
2461
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
res = 0
now = sum(nums[:k-1])
cnt = Counter(nums[:k-1])
for i , out in zip(nums[k-1:], nums):
now += i
cnt[i] += 1
if len(cnt) == k:
res = max(res, now)
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out]
now -= out
return res
1423
思路：分别进行正向和逆向两次滑动窗口，找出最大值。
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
if k == 1:
return max(cardPoints[0],cardPoints[-1])
p1 = k // 2 - 1
p2 = len(cardPoints) - k // 2
res = 0
now = sum(cardPoints[:p1]) + sum(cardPoints[p2:len(cardPoints)])
for i in range(p1, k):
now += cardPoints[i]
if i + len(cardPoints) - p2 < k - 1:
continue
res = max(now, res)
if p2 != len(cardPoints):
now -= cardPoints[p2]
p2 += 1
p1 = k // 2 - 1
p2 = len(cardPoints) - k // 2
now = sum(cardPoints[:p1 + 1]) + sum(cardPoints[p2 + 1:len(cardPoints)])
for i in range(p2, len(cardPoints) - k - 1, -1):
now += cardPoints[i]
if p1 + len(cardPoints) - i < k - 1:
continue
res = max(now, res)
if p1 >= 0:
now -= cardPoints[p1]
p1 -= 1
return res
1652
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
if k == 0:
for i in range(n):
code[i] = 0
return code
arr = []
if k < 0:
k = -k
for i in range(n):
num = 0
for j in range(1,k + 1):
num += code[(i - j + n)%n]
arr.append(num)
return arr
else:
for i in range(n):
num = 0
for j in range(1,k + 1):
num += code[(i + j)%n]
arr.append(num)
return arr