What is the primary pattern to solve the Alternating Groups II problem?

The primary pattern is using a sliding window with running state updates to efficiently check for alternating groups of size k.

How does the circle of tiles impact the problem solution?

The circular arrangement requires special handling of the end and start of the array, ensuring the window can wrap around correctly.

Can I solve this problem with a brute-force approach?

While it's possible to use brute-force, the sliding window approach is more efficient and should be preferred for larger inputs.

How can GhostInterview help with this problem?

GhostInterview helps by guiding you through the sliding window approach, showing you how to optimize the solution and avoid common pitfalls.

What is the time complexity of the solution for Alternating Groups II?

The time complexity is O(n + k), where n is the number of tiles and k is the size of the alternating group.

#3208

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

交替组 II

给你一个整数数组 colors 和一个整数 k ， colors 表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ： colors[i] == 0 表示第 i 块瓷砖的颜色是红色。 colors[i] == 1 表示第 i 块瓷砖的颜色是蓝色。环中连续 k 块…

数组滑动窗口

题目描述

给你一个整数数组 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 <= 10⁵
0 <= colors[i] <= 1
3 <= k <= colors.length

lightbulb

解题思路

方法一：一次遍历

我们可以将环展开成一个长度为 $2n$ 的数组，然后从左到右遍历这个数组，用一个变量 $\textit{cnt}$ 记录当前交替组的长度，如果遇到了相同的颜色，就将 $\textit{cnt}$ 重置为 $1$ ，否则将 $\textit{cnt}$ 加一。如果 $\textit{cnt} \ge k$ ，并且当前位置 $i$ 大于等于 $n$ ，那么就找到了一个交替组，答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{colors}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        ans = cnt = 0
        for i in range(n << 1):
            if i and colors[i % n] == colors[(i - 1) % n]:
                cnt = 1
            else:
                cnt += 1
            ans += i >= n and cnt >= k
        return ans

speed

复杂度分析

指标	值
时间	O(n + k)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should focus on a sliding window approach rather than brute-force checking of all possible groups.
question_mark
They should demonstrate an understanding of the circular nature of the problem and how to handle the edge cases effectively.
question_mark
Look for clear, incremental updates to the window state and a focus on efficiency rather than recalculating the entire window on each iteration.

warning

常见陷阱

外企场景

error
Failing to handle the circular nature of the problem, resulting in incorrect group counting when crossing the array's boundary.
error
Not updating the window state efficiently, leading to unnecessary recomputations.
error
Incorrectly assuming that the first and last tiles in the group do not need to alternate in color when checking for groups.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjusting the group size k dynamically based on input constraints.
arrow_right_alt
Expanding the problem to handle groups with more than two colors.
arrow_right_alt
Optimizing the approach further for arrays with larger sizes, using parallel processing techniques.

help

常见问题

外企场景

继续练习

#3206 交替组 I #3191 使二进制数组全部等于 1 的最少操作次数 I #3254 长度为 K 的子数组的能量值 I