What is an alternating group in Alternating Groups I?

An alternating group is a sequence of three tiles where the middle tile differs from its immediate neighbors in a circular array.

How do I handle the circular array when checking groups?

Use modulo arithmetic to wrap around the array ends so the first and last tiles are considered neighbors.

Can I solve this without a sliding window?

Yes, but a sliding window with running updates reduces redundant checks and keeps time complexity O(n).

What is the time complexity for Alternating Groups I?

The sliding window approach checks each tile once, so the time complexity is O(n) with constant space.

Does GhostInterview detect common pitfalls for this problem?

Yes, it highlights issues like missed circular boundaries, miscounting middle tiles, and redundant recalculations.

#3206

Easy

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

LeetCode 题解工作台

交替组 I

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

数组滑动窗口

题目描述

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

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

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

请你返回交替组的数目。

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

示例 1：

输入：colors = [1,1,1]

输出：0

解释：

示例 2：

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

输出：3

解释：

交替组包括：

提示：

3 <= colors.length <= 100
0 <= colors[i] <= 1

lightbulb

解题思路

方法一：一次遍历

我们令 $k = 3$ ，表示交替组的长度为 $3$ 。

为了方便处理，我们可以将环展开成一个长度为 $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

13

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        k = 3
        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

复杂度分析

指标	值
时间	complexity is O(n) since each tile is checked once in a sliding window. Space complexity is O(1) as only counters and indices are maintained without extra arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can you apply a sliding window instead of nested loops?
question_mark
How do you handle the circular nature of the array?
question_mark
Are you updating counts efficiently without redundant recalculations?

warning

常见陷阱

外企场景

error
Forgetting the circular wrap-around, causing missed groups at array ends.
error
Incorrectly comparing tiles without considering the middle tile distinction.
error
Recomputing full windows instead of using running updates, increasing time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count alternating groups of size 4 instead of 3 in a circular array.
arrow_right_alt
Use more than two colors and identify alternating patterns.
arrow_right_alt
Return indices of all alternating groups instead of just the count.

help

常见问题

外企场景

继续练习

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