算法题记录 30

滑动窗口

1456.定长子串中元音的最大数目（1263）

给你字符串 s 和整数 k 。

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

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

涉及知识点

滑动窗口

解决思路

最基本的固定滑动窗口

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        count=0
        ans=0
        for i,c in enumerate(s):
            if c in "aeiou":
                count+=1
            if i<k-1:
                continue
            ans=max(ans,count)
            if s[i-k+1] in "aeiou":
                count-=1
        return ans

643.子数组最大平均数1（简单）

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

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

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

涉及知识点

滑动窗口

解决思路

最基本的固定滑动窗口

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        count=0
        ans=-inf
        for i,n in enumerate(nums):
            count+=n
            if i<k-1:
                continue
            ans=max(ans,count/k)
            count-=nums[i-k+1]
        return ans

1343.大小为K且平均值大于等于阈值的子数组数目（简单）

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

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

涉及知识点

滑动窗口

解决思路

最基本的固定滑动窗口

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        s=0
        count=0
        for i,n in enumerate(arr):
            s+=n
            if i<k-1:
                continue
            if (s/k)>=threshold:
                count+=1
            s-=arr[i-k+1]
        return count

2090.半径为K的子数组平均值（1358）

给你一个下标从 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 。

涉及知识点

滑动窗口

解决思路

最基本的固定滑动窗口

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        avgs = [-1 for _ in range(len(nums))]
        count = 0
        for i in range(0, len(nums)):
            count += nums[i]
            if i < 2 * k :
                continue
            avgs[i-k] = count // (2 * k + 1)
            count -= nums[i - 2 * k]
        return avgs

每日题

2272.最大波动的子字符串（2516）

给你一个下标从 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 。

涉及知识点

状态机DP

解决思路

有难度

class Solution:
    def largestVariance(self, s: str) -> int:
        ans = 0
        for a, b in permutations(ascii_lowercase, 2):  # 枚举所有小写字母对
            f0, f1 = 0, -inf
            for ch in s:
                if ch == a:
                    f0 = max(f0, 0) + 1
                    f1 += 1
                elif ch == b:
                    f1 = f0 = max(f0, 0) - 1
                # else: f0 = max(f0, 0) 可以留到 ch 等于 a 或者 b 的时候计算，f1 不变
                ans = max(ans, f1)
        return ans

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。