3208. 交替组 II

🟠   🔖  数组 滑动窗口  🔗 力扣 LeetCode

题目

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

Explanation:

Alternating groups:

Example 2:

Input: colors = [0,1,0,0,1,0,1], k = 6

Output: 2

Explanation:

Alternating groups:

Example 3:

Input: colors = [1,1,0,1], k = 4

Output: 0

Explanation:

Constraints:

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

题目大意

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

解释：

交替组包括：

示例 2：

输入： colors = [0,1,0,0,1,0,1], k = 6

输出： 2

解释：

交替组包括：

示例 3：

输入： colors = [1,1,0,1], k = 4

输出： 0

解释：

提示：

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

解题思路

使用 滑动窗口 结合 循环数组索引 来统计满足 k 的子序列数量：

1. 初始化变量：

   • result = 0 记录满足 k 的交替子序列数量。
   • groupLen = 1 记录当前交替子序列的长度。
   • prevColor = colors[0] 记录上一个颜色值。

2. 遍历所有可能的子序列：

   • n 轮遍历：确保每个元素都至少成为 起点 一次。
   • k - 1 额外遍历：确保即使在数组末尾，仍然可以形成长度至少为 k 的交替子序列。
   • 因此，循环条件 i < n + k - 1 让我们 多走 k - 1 步，确保所有可能的 k 长度子序列都被统计到。
   • 计算循环索引 idx = i % n 访问颜色数组。
   • 如果当前颜色和上一个颜色相同，重置 groupLen = 1，重新开始计算交替子序列。
   • 如果当前颜色不同，groupLen++，如果 groupLen >= k，则 result++。

3. 返回 result。

复杂度分析

• 时间复杂度：O(n + k)，遍历 n + k 次。
• 空间复杂度：O(1)，只使用了常数变量。

代码

/**
 * @param {number[]} colors
 * @param {number} k
 * @return {number}
 */
var numberOfAlternatingGroups = function (colors, k) {
	const n = colors.length;
	let result = 0;
	let groupLen = 1;
	let prevColor = colors[0];
	for (let i = 1; i < n + k - 1; i++) {
		let idx = i % n;
		if (prevColor == colors[idx]) {
			groupLen = 1; // 重新开始计算
		} else {
			groupLen++;
			if (groupLen >= k) {
				result++;
			}
		}
		prevColor = colors[idx];
	}
	return result;
};