题目链接
分析
由于题目是中的数组表达的是一个环，所以我们将数组复制一份首尾链接（实际操作中取余即可）
考虑计算交替组，我们可以动态维护一个 $cnt$ 记录到当前位置的交替组的长度
对于每个位置，如果 $cnt >= k$ 则 $ans + 1$
要注意，由于我们将两个数组首尾相连拼在了一起，所以只有当 $i >= n$ ，即走到复制的数组时才开始记录答案
对于第一个数组，由于我们计算答案只从复制的数组第一个数 $n$ 开始，所以循环从 $n - k - 1$ 处开始即可
交替组 I 为 $k = 3$ 的特殊情况
代码实现
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors) {
int ans = 0, cnt = 0, n = colors.size();
for(int i = max(0, n - 4); i < (n << 1); ++i)
{
if(i > 0 && colors[i % n] == colors[(i - 1) % n])
cnt = 0;
cnt++;
ans += i >= n && cnt >= 3;
}
return ans;
}
};
复杂度分析
- 时间复杂度：$O(n)$，$n$ 为 $colors$ 的长度
- 空间复杂度：$O(1)$，实际中并没有真正复制数组
