Leetcode打卡：交替组II

执行结果：通过

题目：3208 交替组II

给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

• colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
• colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

示例 1：

输入：colors = [0,1,0,1,0], k = 3

输出：3

解释：

交替组包括：

示例 2：

输入：colors = [0,1,0,0,1,0,1], k = 6

输出：2

解释：

交替组包括：

示例 3：

输入：colors = [1,1,0,1], k = 4

输出：0

解释：

提示：

• 3 <= colors.length <= 105
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

代码以及解题思路

代码：

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        ans = 0
        start, n = 0, len(colors)
        From_head = True # 从头开始检查是否交替
        while start < n:
            if From_head:
                for i in range(start, start + k - 1):
                    if colors[i%n] == colors[(i+1)%n]:
                        start = i + 1 # 直接跳到i+1，start~i+1的都不合法
                        break
                else: # 当前窗口全交替，下一个只需检查最后两位是否交替
                    ans += 1
                    start += 1
                    From_head = False
            else:
                if colors[(start+k-1)%n] == colors[(start+k-2)%n]:
                    From_head = True
                    start += k - 1
                else:
                    ans += 1
                    start += 1

        return ans

解题思路：

1. 初始化变量：
   • ans：记录满足条件的交替子数组的数量。
   • start：当前滑动窗口的起始位置。
   • n：颜色数组 colors 的长度。
   • From_head：布尔值，表示当前是否从头开始检查整个窗口的交替性。
2. 滑动窗口遍历：
   • 使用一个 while 循环遍历数组，条件是 start < n，确保不会越界。
   • 从头开始检查（From_head = True）：
     • 使用一个 for 循环检查从 start 到 start + k - 1 的窗口内的元素是否交替。
     • 如果在这个窗口内发现相邻元素颜色相同，则更新 start 为 i + 1，并跳出循环，因为当前窗口不满足交替条件，需要从下一个位置重新开始检查。
     • 如果整个窗口检查完毕且满足交替条件，则增加 ans 的值，表示找到了一个满足条件的子数组。
     • 更新 start 为 start + 1，准备检查下一个窗口，并设置 From_head = False，表示下一个窗口只需检查最后两个元素是否交替。
   • 不从头开始检查（From_head = False）：
     • 直接检查当前窗口的最后一个元素和倒数第二个元素是否交替。
     • 如果它们颜色相同，说明当前窗口不满足交替条件，需要将 From_head 设置为 True 并更新 start 为 start + k - 1，准备从头开始检查下一个窗口。
     • 如果它们颜色不同，则增加 ans 的值，并更新 start 为 start + 1，准备检查下一个窗口。
3. 处理周期性边界条件：
   • 在数组遍历中，使用 % n 来处理数组首尾相连的情况，确保索引不会越界。
4. 返回结果：
   • 当 while 循环结束后，返回 ans，即满足条件的交替子数组的数量。