LeetCode 题解工作台
交替组 III
给你一个整数数组 colors 和一个二维整数数组 queries 。 colors 表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ： colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。 colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 …
2
题型
0
代码语言
3
相关题
当前训练重点
困难 · 数组·结合·二分·indexed·树
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·二分·indexed·树 题型思路
题目描述
给你一个整数数组 colors 和一个二维整数数组 queries 。colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：
colors[i] == 0表示第i块瓷砖的颜色是 红色 。colors[i] == 1表示第i块瓷砖的颜色是 蓝色 。
环中连续若干块瓷砖的颜色如果是 交替 颜色（也就是说这组瓷砖中除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替组。
你需要处理两种类型的查询：
queries[i] = [1, sizei]，确定大小为sizei的 交替组 的数量。queries[i] = [2, indexi, colori]，将colors[indexi]更改为colori。
返回数组 answer，数组中按顺序包含第一种类型查询的结果。
注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
示例 1：
输入：colors = [0,1,1,0,1], queries = [[2,1,0],[1,4]]
输出：[2]
解释：
第一次查询：
将 colors[1] 改为 0。
第二次查询：
统计大小为 4 的交替组的数量：
示例 2：
输入：colors = [0,0,1,0,1,1], queries = [[1,3],[2,3,0],[1,5]]
输出：[2,0]
解释：
第一次查询：
统计大小为 3 的交替组的数量。
第二次查询：colors不变。
第三次查询：不存在大小为 5 的交替组。
提示：
4 <= colors.length <= 5 * 1040 <= colors[i] <= 11 <= queries.length <= 5 * 104queries[i][0] == 1或queries[i][0] == 2- 对于所有的
i：queries[i][0] == 1：queries[i].length == 2,3 <= queries[i][1] <= colors.length - 1queries[i][0] == 2：queries[i].length == 3,0 <= queries[i][1] <= colors.length - 1,0 <= queries[i][2] <= 1
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depends on the implementation of the Binary Indexed Tree and updates. Efficient BIT operations keep each query around O(log n) for both updates and counts, avoiding O(n) scans. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting you to optimize alternating sequence tracking rather than naive array scans.
- question_mark
Watch for updates that affect multiple overlapping groups in the circular array.
- question_mark
Correctly applying a BIT to this array pattern signals strong data structure insight.
常见陷阱
外企场景- error
Neglecting the circular nature of the array when updating alternating groups.
- error
Recomputing the full array for every query instead of updating affected ranges.
- error
Miscounting groups when adjacent tiles change color and merge or split groups.
进阶变体
外企场景- arrow_right_alt
Queries could ask for maximal alternating group length instead of counts.
- arrow_right_alt
The array may include more than two colors, requiring generalization of alternation rules.
- arrow_right_alt
Allowing multiple color changes in one query to test batch update efficiency in BIT.