LeetCode 每日一题 24.11.27

3208. 交替组 II

给你一个整数数组 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 <= 105
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

模拟做法：

通过符合要求累加的形式，符合则累加计算长度（即符合的个数为长度m-k+1个），不符合则重置为1。复杂度O(n+k)

注：枚举长度为n+k-2，第一次区间是[0,k-1],……,第n个区间是[n-1,n+k-2]。

	public int numberOfAlternatingGroups(int[] colors, int k) {
		int sum = 0, ans = 1;
		int n = colors.length;
		for (int i = 0 ; i < n + k - 2 ; i++) {
			if (colors[i % n] != colors[(i + 1) % n]) {
				ans++;
			}
			else {
				ans = 1;
			}
			if (ans >= k) {
				sum++;
			}
		}
		return sum;
	}

可重新写：

public int numberOfAlternatingGroups(int[] colors, int k) {
		int sum = 0, ans = 1;
		int n = colors.length;
		for (int i = 0 ; i < n + k - 2 ; i++) {
			if (colors[i % n] != colors[(i + 1) % n]) {
				ans++;
			}
			else {
				sum += Math.max(ans - k + 1, 0);
				ans = 1;
			}
		}
		return sum + Math.max(ans - k + 1, 0);
	}

前缀和做差做法：

利用前缀和特性，累计前i个符合条件的个数，再通过距离k做差。复杂度O(n+k)

	public int numberOfAlternatingGroups(int[] colors, int k) {
		int n = colors.length;
		int[] prefix = new int[n + k - 1];
		Arrays.fill(prefix, 1);
		for (int i = 1 ; i < n + k - 1 ; i++) {
			prefix[i] = prefix[i - 1] + (colors[i % n] != colors[(i - 1) % n] ? 1 : 0);
		}
		int sum = 0;
		for (int i = k - 1 ; i < n + k - 1 ; i++) {
			if (prefix[i] - prefix[i - k + 1] >= k - 1) {
				sum++;
			}
		}
		return sum;
	}