【LetMeFly】3208.交替组 II：滑动窗口
力扣题目链接：https://leetcode.cn/problems/alternating-groups-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 <= 1050 <= colors[i] <= 13 <= k <= colors.length
解题方法：滑动窗口
使用一个大小为k的“窗口”，统计窗口中“相邻两个元素不相同”的个数。
从$0$到$len(colors) - 1$遍历“窗口”的起点，每次起点向后移动一位，终点也向后移动一位（记得对$len(colors)$取模）。
窗口每移动一次，就依据新加入窗口的“相邻元素对”和刚移出窗口的“相邻元素对”更新窗口中“相邻两个元素不相同”的个数。
每次窗口中“相邻两个元素不相同”的个数若为$k - 1$，则说明是一个符合要求的窗口，答案数量加一。
- 时间复杂度$O(len(colors))$
- 空间复杂度$O(1)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int ans = 0;
int cntDiff = 0;
for (int i = 1; i < k; i++) {
if (colors[i] != colors[i - 1]) {
cntDiff++;
}
}
for (int i = 0; i < colors.size(); i++) {
ans += cntDiff == k - 1;
cntDiff += colors[(i + k) % colors.size()] != colors[(i + k - 1) % colors.size()];
cntDiff -= colors[(i + 1) % colors.size()] != colors[i];
}
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
| from typing import List
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
ans = 0
cntDiff = sum(colors[i] != colors[i - 1] for i in range(1, k))
for i in range(len(colors)):
ans += cntDiff == k - 1
cntDiff += colors[(i + k) % len(colors)] != colors[(i + k - 1) % len(colors)]
cntDiff -= colors[(i + 1) % len(colors)] != colors[i]
return ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int ans = 0;
int cntDiff = 0;
for (int i = 1; i < k; i++) {
if (colors[i] != colors[i - 1]) {
cntDiff++;
}
}
for (int i = 0; i < colors.length; i++) {
if (cntDiff == k - 1) {
ans++;
}
if (colors[(i + k) % colors.length] != colors[(i + k - 1) % colors.length]) {
cntDiff++;
}
if (colors[(i + 1) % colors.length] != colors[i]) {
cntDiff--;
}
}
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| package main
func numberOfAlternatingGroups(colors []int, k int) (ans int) {
cntDiff := 0
for i := 1; i < k; i++ {
if colors[i] != colors[i - 1] {
cntDiff++
}
}
for i := range colors {
if cntDiff == k - 1 {
ans++
}
if colors[(i + k) % len(colors)] != colors[(i + k - 1) % len(colors)] {
cntDiff++
}
if colors[(i + 1) % len(colors)] != colors[i] {
cntDiff--
}
}
return
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/144123453