题目描述
给你一个整数数组 colors
和一个整数 k
,colors
表示一个由红色和蓝色瓷砖组成的环,第 i
块瓷砖的颜色为 colors[i]
:
colors[i] == 0
表示第i
块瓷砖的颜色是 红色。colors[i] == 1
表示第i
块瓷砖的颜色是 蓝色。
环中连续 k
块瓷砖的颜色如果是 交替 颜色(也就是说除了第一块和最后一块瓷砖以外,中间瓷砖的颜色与它 左边 和 右边 的颜色都不同),那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意,由于 colors
表示一个 环,第一块 瓷砖和 最后一块 瓷砖是相邻的。
样例
输入:colors = [0,1,0,1,0], k = 3
输出:3
解释:
交替组包括:
输入:colors = [0,1,0,0,1,0,1], k = 6
输出:2
解释:
交替组包括:
输入:colors = [1,1,0,1], k = 4
输出:0
解释:
限制
3 <= colors.length <= 10^5
0 <= colors[i] <= 1
3 <= k <= colors.length
算法1
(思维题) $O(n)$
- 将每个位置根据「是否与上一个位置不同」修改值。如果不同,则为 1,否则为 0。注意环的处理。
- 修改后,找到某一个值为 0 的位置当做初始位置。如果不存在,直接返回 $n$。
- 从初始位置开始,遍历环一次,期间任何连续超过 $k - 1$ 个 $1$,都可以对应到一个替换组上,答案加 1。
时间复杂度
- 遍历环状数组三次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
const int n = colors.size();
int t = colors[0];
for (int i = 0; i < n - 1; i++)
colors[i] = colors[i] != colors[i + 1];
colors[n - 1] = colors[n - 1] != t;
int st = -1;
for (int i = 0; i < n; i++)
if (colors[i] == 0) {
st = i;
break;
}
if (st == -1)
return n;
int i = st, c = 0, ans = 0;
do {
if (colors[i] == 1) ++c;
else c = 0;
if (c >= k - 1)
++ans;
i = (i + 1) % n;
} while (i != st);
return ans;
}
};
算法2
(思维题) $O(n)$
- 可以考虑求出以 $i$ 为结尾时尽可能小的 $j$,满足 $[j, i], [j + 1, i], \dots, [i, i]$ 都是交替数组。
- 由于是环状的,所以 $i$ 需要遍历到 $2n$。
- 当 $i \ge n$ 且 $[j, i]$ 的长度大于等于 $k$ 时,可以累加答案。$i \ge n$ 的限制是因为避免在 $i \ge n$ 时重复计算 $i < n$ 时的答案。
时间复杂度
- 遍历环状数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
const int n = colors.size();
int ans = 0;
for (int i = 1, j = 0; i < 2 * n; i++) {
if (colors[i % n] == colors[(i - 1) % n])
j = i;
if (i >= n && i - j + 1 >= k)
++ans;
}
return ans;
}
};