[LeetCode] 3208. Alternating Groups II

There is a circle of red and blue tiles. You are given an array of integers colors and an integer k. The color of tile i is represented by colors[i]:
colors[i] == 0 means that tile i is red.
colors[i] == 1 means that tile i is blue.
An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).

Return the number of alternating groups.

Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.

Example 1:
Input: colors = [0,1,0,1,0], k = 3
Output: 3

Example 2:
Input: colors = [0,1,0,0,1,0,1], k = 6
Output: 2

Example 3:
Input: colors = [1,1,0,1], k = 4
Output: 0

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

交替组 II。

给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

思路

思路同版本一 3206，只是这次是 k 个元素的窗口。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
		// 目前子数组的长度
        int count = 1;
        int res = 0;
        for (int i = 1; i < n + k - 1; i++) {
            int cur = colors[i % n];
            int prev = colors[(i - 1) % n];
            if (cur != prev) {
                count++;
            } else {
                count = 1;
            }
			// 如果子数组长度大于等于k，那么就是一个满足题意的alternating group
            if (count >= k) {
                res++;
            }
        }
        return res;
    }
}

相关题目

3101. Count Alternating Subarrays
3206. Alternating Groups I
3208. Alternating Groups II