交替组
[3206]交替组I
题目描述
给你一个整数数组 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
交替组如下：
题解
我们可以通过以下的步骤来实现：
- 遍历数组，考虑当前位置及其前后两块瓷砖。
- 对于位置
i，检查三个位置i-1,i,i+1的颜色是否满足交替组的条件。 - 由于是环形结构，需要特别处理数组的头尾部分。
public int numberOfAlternatingGroups(int[] colors) {
int ans = 0;
int n = colors.length;
for (int i = 0; i < n; i++) {
if (colors[i] != colors[(i + 1) % n] &&
colors[(i + 1) % n] != colors[(i + 2) % n]) {
ans++;
}
}
return ans;
}
[3207]交替组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
题解
思路和上面的基本一样：
- 外层循环：遍历数组中的每个起始位置
i。 - 内层循环：检查从当前位置
i开始的k个瓷砖是否满足交替条件。对于每个瓷砖，检查它与左右瓷砖的颜色是否不同（除了第一块和最后一块瓷砖）。 - 模运算：使用
colors[(i + j) % n]来确保数组的环形结构。
public int numberOfAlternatingGroups(int[] colors, int k) {
int ans = 0;
int n = colors.length;
for (int i = 0; i < n; i++) {
// 检查从位置 i 开始的 k 个瓷砖是否满足交替条件
boolean flag = true;
for (int j = 0; j < k; j++) {
// 检查第 j 块瓷砖与它的前后瓷砖颜色是否不同
int prev = Math.floorMod(i + j - 1, n);
int current = Math.floorMod(i + j, n);
int next = Math.floorMod(i + j + 1, n);
// 如果不是第一块瓷砖或者最后一块瓷砖，则需要检查前后瓷砖的颜色
if (j != 0 && j != k - 1) {
if (colors[current] == colors[prev] || colors[current] == colors[next]) {
flag = false;
break;
}
}
}
if (flag) ans++;
}
return ans;
}
但这样需要双重循环，时间复杂度过高。
我们可以将环展开成一个长度为2n的数组，然后从左到右遍历这个数组，用一个变量记录当前交替组的长度，如果遇到了相同的颜色，就将当前交替组的长度重置为 1，否则加一。
如果交替组的长度大于k，并且当前位置i大于等于n，那么就找到了一个交替组，答案加一。
public int numberOfAlternatingGroups(int[] colors, int k) {
int ans = 0;
int n = colors.length;
// 记录交替组的长度
int currentLength = 0;
for (int i = 0; i < 2 * n; ++i) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
currentLength = 1;
} else {
currentLength++;
}
if (i >= n && currentLength >= k) ans++;
}
return ans;
}