题目描述
给你一个整数数组 colors
,它表示一个由红色和蓝色瓷砖组成的环,第 i
块瓷砖的颜色为 colors[i]
:
colors[i] == 0
表示第i
块瓷砖的颜色是 红色。colors[i] == 1
表示第i
块瓷砖的颜色是 蓝色。
环中连续 3 块瓷砖的颜色如果是 交替 颜色(也就是说中间瓷砖的颜色与它 左边 和 右边 的颜色都不同),那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意,由于 colors
表示一个 环,第一块 瓷砖和 最后一块 瓷砖是相邻的。
样例
输入:colors = [1,1,1]
输出:0
解释:
输入:colors = [0,1,0,0,1]
输出:3
解释:
交替组包括:
限制
3 <= colors.length <= 100
0 <= colors[i] <= 1
算法
(暴力枚举) $O(n)$
- 暴力枚举每个位置,如果其与前后位置的颜色都不一样,则答案加 1。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors) {
const int n = colors.size();
int ans = 0;
for (int i = 0; i < n; i++) {
int x = colors[i];
int y = colors[(i - 1 + n) % n];
int z = colors[(i + 1) % n];
if (x != y && x != z)
++ans;
}
return ans;
}
};