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

解释：

交替组包括：

提示：

3 <= colors.length <= 100
0 <= colors[i] <= 1

解法

方法一：一次遍历

思考

\(n\le 100\) 且组长度固定为 \(3\)，枚举每个起点再检查三格是否交替即可。环上越界需要取模，写法略繁。

将环展开为长度 \(2n\) 的线性扫描后，用 \(\textit{cnt}\) 记录当前交替段长度，相邻同色则重置。仅当 \(i\ge n\) 且 \(\textit{cnt}\ge 3\) 时计入，从而每个原位置作为组的右端点恰好统计一次，额外空间 \(O(1)\)。

我们令 \(k = 3\)，表示交替组的长度为 \(3\)。

为了方便处理，我们可以将环展开成一个长度为 \(2n\) 的数组，然后从左到右遍历这个数组，用一个变量 \(\textit{cnt}\) 记录当前交替组的长度，如果遇到了相同的颜色，就将 \(\textit{cnt}\) 重置为 \(1\)，否则将 \(\textit{cnt}\) 加一。如果 \(\textit{cnt} \ge k\)，并且当前位置 \(i\) 大于等于 \(n\)，那么就找到了一个交替组，答案加一。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{colors}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        k = 3
        n = len(colors)
        ans = cnt = 0
        for i in range(n << 1):
            if i and colors[i % n] == colors[(i - 1) % n]:
                cnt = 1
            else:
                cnt += 1
            ans += i >= n and cnt >= k
        return ans

class Solution {
    public int numberOfAlternatingGroups(int[] colors) {
        int k = 3;
        int n = colors.length;
        int ans = 0, cnt = 0;
        for (int i = 0; i < n << 1; ++i) {
            if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
                cnt = 1;
            } else {
                ++cnt;
            }
            ans += i >= n && cnt >= k ? 1 : 0;
        }
        return ans;
    }
}

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors) {
        int k = 3;
        int n = colors.size();
        int ans = 0, cnt = 0;
        for (int i = 0; i < n << 1; ++i) {
            if (i && colors[i % n] == colors[(i - 1) % n]) {
                cnt = 1;
            } else {
                ++cnt;
            }
            ans += i >= n && cnt >= k ? 1 : 0;
        }
        return ans;
    }
};

func numberOfAlternatingGroups(colors []int) (ans int) {
    k := 3
    n := len(colors)
    cnt := 0
    for i := 0; i < n<<1; i++ {
        if i > 0 && colors[i%n] == colors[(i-1)%n] {
            cnt = 1
        } else {
            cnt++
        }
        if i >= n && cnt >= k {
            ans++
        }
    }
    return
}

function numberOfAlternatingGroups(colors: number[]): number {
    const k = 3;
    const n = colors.length;
    let [ans, cnt] = [0, 0];
    for (let i = 0; i < n << 1; ++i) {
        if (i && colors[i % n] === colors[(i - 1) % n]) {
            cnt = 1;
        } else {
            ++cnt;
        }
        ans += i >= n && cnt >= k ? 1 : 0;
    }
    return ans;
}

3206. 交替组 I

题目描述

解法

方法一：一次遍历

评论