Hard
题目描述
有一些红色和蓝色的瓦片围成一个圆形排列。给你一个整数数组 colors 和一个二维整数数组 queries。
瓦片 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]
示例 2：
输入：colors = [0,0,1,0,1,1], queries = [[1,3],[2,3,0],[1,5]]
输出：[2,0]
提示：
- 4 <= colors.length <= 5 * 10^4
- 0 <= colors[i] <= 1
- 1 <= queries.length <= 5 * 10^4
- queries[i][0] == 1 或 queries[i][0] == 2
解题思路
这道题目需要高效处理两种操作：查询特定大小的交替组数量和修改颜色。关键思路如下：
核心观察：
- 交替组是连续的颜色交替序列，我们需要找到所有最大交替段
- 对于长度为 len 的最大交替段，它包含 max(0, len - k + 1) 个长度为 k 的交替组
- 由于数组是环形的，需要特殊处理边界情况
算法步骤：
- 使用多重集合（multiset）维护所有最大交替段的长度
- 对于查询类型1：遍历所有段长度，计算能贡献多少个指定大小的交替组
- 对于查询类型2：更新颜色后，重新计算受影响的交替段
实现细节：
- 首先找到所有最大交替段并存储其长度
- 修改颜色时，需要移除旧段、计算新段并更新multiset
- 环形数组的处理：当所有元素都交替时，整个数组形成一个大的交替组
时间优化： 使用multiset可以快速插入、删除和遍历段长度，每次查询的时间复杂度为 O(段数量)，修改操作为 O(log n)。
代码实现
class Solution {
public:
vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {
int n = colors.size();
multiset<int> segments;
// Find all maximal alternating segments
auto findSegments = [&]() {
segments.clear();
if (n == 0) return;
// Check if all elements are alternating
bool allAlternating = true;
for (int i = 0; i < n; i++) {
if (colors[i] == colors[(i + 1) % n]) {
allAlternating = false;
break;
}
}
if (allAlternating) {
segments.insert(n);
return;
}
// Find segments
for (int i = 0; i < n; i++) {
if (colors[i] == colors[(i + 1) % n]) {
int start = (i + 1) % n;
int len = 1;
int j = start;
while (colors[j] != colors[(j + 1) % n] && (j + 1) % n != start) {
len++;
j = (j + 1) % n;
}
if (len >= 3) {
segments.insert(len);
}
i = j;
}
}
};
findSegments();
vector<int> result;
for (auto& query : queries) {
if (query[0] == 1) {
int k = query[1];
int count = 0;
for (int len : segments) {
if (len >= k) {
count += len - k + 1;
}
}
result.push_back(count);
} else {
int index = query[1];
int newColor = query[2];
if (colors[index] != newColor) {
colors[index] = newColor;
findSegments();
}
}
}
return result;
}
};
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
from collections import Counter
n = len(colors)
segments = Counter()
def find_segments():
segments.clear()
if n == 0:
return
# Check if all elements are alternating
all_alternating = True
for i in range(n):
if colors[i] == colors[(i + 1) % n]:
all_alternating = False
break
if all_alternating:
segments[n] += 1
return
# Find segments
i = 0
while i < n:
if colors[i] == colors[(i + 1) % n]:
start = (i + 1) % n
length = 1
j = start
while colors[j] != colors[(j + 1) % n] and (j + 1) % n != start:
length += 1
j = (j + 1) % n
if length >= 3:
segments[length] += 1
i = j
else:
i += 1
find_segments()
result = []
for query in queries:
if query[0] == 1:
k = query[1]
count = 0
for length, freq in segments.items():
if length >= k:
count += (length - k + 1) * freq
result.append(count)
else:
index = query[1]
new_color = query[2]
if colors[index] != new_color:
colors[index] = new_color
find_segments()
return result
public class Solution {
public IList<int> NumberOfAlternatingGroups(int[] colors, int[][] queries) {
int n = colors.Length;
var segments = new Dictionary<int, int>();
void FindSegments() {
segments.Clear();
if (n == 0) return;
// Check if all elements are alternating
bool allAlternating = true;
for (int i = 0; i < n; i++) {
if (colors[i] == colors[(i + 1) % n]) {
allAlternating = false;
break;
}
}
if (allAlternating) {
segments[n] = segments.GetValueOrDefault(n, 0) + 1;
return;
}
// Find segments
for (int i = 0; i < n; i++) {
if (colors[i] == colors[(i + 1) % n]) {
int start = (i + 1) % n;
int len = 1;
int j = start;
while (colors[j] != colors[(j + 1) % n] && (j + 1) % n != start) {
len++;
j = (j + 1) % n;
}
if (len >= 3) {
segments[len] = segments.GetValueOrDefault(len, 0) + 1;
}
i = j;
}
}
}
FindSegments();
var result = new List<int>();
foreach (var query in queries) {
if (query[0] == 1) {
int k = query[1];
int count = 0;
foreach (var kvp in segments) {
if (kvp.Key >= k) {
count += (kvp.Key - k + 1) * kvp.Value;
}
}
result.Add(count);
} else {
int index = query[1];
int newColor = query[2];
if (colors[index] != newColor) {
colors[index] = newColor;
FindSegments();
}
}
}
return result;
}
}
var numberOfAlternatingGroups = function(colors, queries) {
const n = colors.length;
const result = [];
function countAlternatingGroups(size) {
if (size > n) return 0;
let count = 0;
for (let i = 0; i < n; i++) {
let isAlternating = true;
for (let j = 1; j < size; j++) {
const curr = (i + j) % n;
const prev = (i + j - 1) % n;
if (colors[curr] === colors[prev]) {
isAlternating = false;
break;
}
}
if (isAlternating) count++;
}
return count;
}
for (const query of queries) {
if (query[0] === 1) {
const size = query[1];
result.push(countAlternatingGroups(size));
} else {
const index = query[1];
const color = query[2];
colors[index] = color;
}
}
return result;
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化段 | O(n) | O(k) |
| 查询类型1 | O(k) | O(1) |
| 修改类型2 | O(n) | O(1) |
| 总体 | O(q × n) | O(n) |
其中 n 是 colors 数组长度，q 是查询数量，k 是不同段长度的数量（最多 O(n)）。