灵神基础讲解

核心思想

1456.定长字串中元音的最大数目

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

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

定长滑动窗口

灵神总结三步走：

1. 入：下标为i的元素进入窗口，更新统计量。如果i<k-1，说明窗口长度还得加，重复第一步，令更多元素进入窗口
2. 更新：更新答案，一般是更新最大值最小值
3. 出：下标为i-k+1的元素离开窗口，更新相关统计量

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        res = 0  # 最终答案
        val = 0  # 当前窗口的元音数
        # 下标i与字符cur
        for i, cur in enumerate(s):
            # 第一步：进入窗口
            if cur in 'aeiou':
                val += 1
            if i < k - 1: # 窗口大小不足k
                continue
            # 第二步：更新答案
            res = max(res, val)
            # 第三步：离开窗口
            if s[i-k+1] in 'aeiou':
                val -= 1
        return res

• 示例1，s = abciiidef，k = 3
  1. 从左到右遍历s
  2. i=0，s[0]=a进入窗口，val=1，i<3-1=2
  3. i=1，s[1]=b进入窗口，但不是元音，val=1,i<3-1=2
  4. i=2，s[2]=c进入窗口，但不是元音，val=1,不再continue，计算s[a]离开窗口的情况，val=0，但是res=1，所以第三步更新后，res保留了当前最大结果，val却更新为k-1的窗口大小情况，更新了离开i-k+1的情况！
  5. i=3，s[3]=i进入窗口，是窗口…

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

643.子数组的最大平均数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

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

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

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

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

2090. 半径为 k 的子数组平均值

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

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大于n
        if k>n:
            return res

        val = 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 res

        val = 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
——————————————————————————————————
通过
        

2379. 得到 K 个黑块的最少涂色次数

给你一个长度为 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 = 0

        for cur in enumerate(blocks):
            if cur == 'B':
                black_val += 1
                if black_val >= k:
                    return 0
            if cur == 'W':
                black_val = 0
            



        for i, cur in enumerate(blocks):
            # 1. 进入窗口
            if cur == 'W': # 如果当前字符cur时白块，增加一次涂色次数
                white_val += 1
            # 如果是黑块，不增加涂色次数，忽略，不用体现在代码中
            # 如果当前窗口长度（i从0开始索引，i时实际上长度是i+1）还没到k，故i+1<k
            if i < k - 1:
                continue # 继续进入窗口，不用 找答案 与 退出窗口
            # 2. 更新答案
            res = min(res, white_val)
            # 3. 退出窗口
            if blocks[i-k-1] == 'W':
                white_val -= 1
        return 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 += 1
            else:
                # 2. 更新答案
                res = min(res, white_val)
                # 退出窗口并进入下一个窗口
                if blocks[i - k] == 'W':
                    white_val -= 1
                if cur == 'W':
                    white_val += 1

        return 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 += 1
                    res = 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 += 1
                    res = white_val
            else:      # 窗口长度达标
                # 2. 更新答案
                res = min(res, white_val)
                # 退出窗口，并且进入下一个窗口
                if blocks[i - k] == 'W':
                    white_val -= 1
                if 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 += 1
                if black_val >= k:
                    return 0
            if 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 += 1
                    res = white_val
            else:      # 窗口长度达标
                # 2. 更新答案
                res = min(res, white_val)
                # 退出窗口，并且进入下一个窗口
                if blocks[i - k] == 'W':
                    white_val -= 1
                if 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一、你解题过程中的错误及修改

• 错误总结：
  • 用错判断相等运算符，该用“==”却用了“is”。
  • 有多余的初始遍历逻辑，和后续滑动窗口逻辑脱节且有问题。
  • 窗口滑动逻辑不完善，没全面考虑白块黑块数量变化对结果影响。
  • 没处理字符串长度等于k且全是黑块的特殊情况。
• 修改过程：发现问题后逐步改，先修正运算符，再补窗口逻辑，最后加特殊情况处理，因没整体梳理逻辑，多次尝试才通过所有测试用例。

二、灵神答案思路

• 先算出字符串前k个字符里白块数量，赋给ans（记录最少涂色次数）和cnt_w（实时统计窗口白块数）。
• 用zip同时遍历从第k个字符起的子串和原串，根据新入和离开窗口的字符更新cnt_w，再更新ans取最小值。
• 最后返回ans，即得到k个连续黑块的最少涂色次数。

．．．主要还是对python的函数ｚｉｐ使用不熟练！也不知道能直接嗲用ｃｏｕｎｔ计算＇Ｗ个数！

1052.爱生气的书店老板

有一个书店老板，他的书店开了 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 = 0

        for 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_peo
        for 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

1461.检查一个字符串是否包含全部长度为k的二进制子串

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

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

1. 代码功能

判断给定二进制字符串 s 是否包含所有长度为 k 的二进制子串。

2. 关键数据结构：集合（set）

• 特点：无序且元素唯一，自动去除重复元素。
• 作用：在此代码中用于存储字符串 s 中不同的长度为 k 的子串，方便去重统计。

3. 主要操作及知识点

循环遍历字符串

• 代码：for i in range(len(s) - k + 1):
• 重点：通过 range() 函数生成合适的整数序列来确定遍历字符串 s 的起始位置，以获取所有可能的长度为 k 的子串。len(s) 是字符串 s 的长度，这里确保能遍历到所有可生成指定长度子串的起始位置。

字符串切片获取子串

• 代码：s[i:i + k]
• 重点：这是Python中字符串切片操作，用于从字符串 s 中取出以 i 为起始位置、长度为 k 的子串，作为后续添加到集合中的元素。

集合添加元素

• 代码：key.add(s[i:i + k])
• 重点：使用集合的 add() 方法将获取到的子串添加到集合 key 中。由于集合特性，重复子串只会添加一次，实现去重效果，最终集合 key 存储的是不同的长度为 k 的子串。

比较判断

• 代码：return len(key) == 1 << k
• 重点：
  • len(key) 获取集合 key 中元素个数，即字符串 s 中实际出现的不同长度为 k 的子串数量。
  • 1 << k 利用左移运算符 << 计算出所有可能的长度为 k 的二进制子串总数（等同于 2 ** k）。
  • 通过比较两者是否相等来判断字符串 s 是否包含所有长度为 k 的二进制子串，相等则返回 True，否则返回 False。
    左移运算符 << 是许多编程语言（包括Python、C、C++、Java等）中用于整数类型的一种位运算操作符。它的主要作用是对一个整数的二进制表示形式进行移位操作，具体解释如下：

基本运算规则

将一个整数的二进制位向左移动指定的位数，右边空出的位用 0 填充。例如，对于整数 a，执行 a << n（这里 n 为要移动的位数）的操作，就是把 a 的二进制表示中的每一位都向左移动 n 位，右边新空出来的 n 个位都用 0 填充。

示例说明

假设我们有一个整数 5，它的二进制表示为 00000101（这里为了方便说明，使用了8位二进制表示，实际在不同编程语言中可能根据整数类型的不同有不同的二进制位数表示，但原理相同）。

• 如果对 5 执行 5 << 1（即向左移动 1 位）的操作：

  • 首先将 5 的二进制 00000101 向左移动 1 位，得到 00001010。
  • 按照二进制转十进制的计算方法（从右到左用二进制的每个数去乘以 $2$ 的相应次方，然后将结果相加），00001010 转换为十进制就是 $2^3+2^1=8+2=10$。所以 5 << 1 的结果是 10。

• 如果对 5 执行 5 << 2（向左移动 2 位）的操作：

  • 把 5 的二进制 00000101 向左移动 2 位，变为 00010100。
  • 再将 00010100 转换为十进制，即 $2^4+2^2=16+4=20$。所以 5 << 2 的结果是 20。

数学等效关系

从数学角度来看，对于整数 a，执行 a << n 的操作，其结果在数值上等同于将 a 乘以 $2^n$。例如上面的例子中，5 << 1 等同于 $5\times 2^1=10$，5 << 2 等同于 $5\times 2^2=20$。

在实际编程中，左移运算符常被用于一些需要快速进行乘法运算（特别是乘以 $2$ 的幂次方）的场景，因为位运算在计算机底层执行速度相对较快，可以在一定程度上提高程序的运算效率。同时，在一些涉及到二进制数据处理、内存地址偏移等方面也经常会用到左移运算符。