交替组II

2024-11-27

leetcode

题目：

给你一个整数数组 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

解释：

交替组包括：

提示：

3 <= colors.length <= 105
0 <= colors[i] <= 1
3 <= k <= colors.length

暴力枚举

思路：

以数组的每一个元素为开头，判断接下去有没有k个交替即可

代码：

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

模拟

思路：

遍历数组 colors，用一个整数 cnt 代表遍历到当前元素时，已经有的连续交替瓷砖的数量。如果当前元素与前一个元素不同，则将 cnt 加 1，否则将其置为 1。 如果当前 cnt 大于等于 k，则将结果加 1。注意到瓷砖是环形的，因此，在遍历第一个数组时，我们就需要知道当前的 cnt。为了得到初始的 cnt 值，我们需要将遍历的起点往前推 k−2 步，这样在遍历到数组的第一个元素时，我们就可以知道当前是否有 k 块连续的交替瓷砖。最后返回结果。

代码：

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