LeetCode 3208.交替组 II：滑动窗口
【LetMeFly】3208.交替组 II：滑动窗口力扣题目链接：https://leetcode.cn/problems/alternating-groups-ii/
给你一个整数数组 colors 和一个整数 k ，colors表示一个由赤色和蓝色瓷砖构成的环，第 i 块瓷砖的颜色为 colors ：
[*]colors == 0 表示第 i 块瓷砖的颜色是 赤色 。
[*]colors == 1 表示第 i 块瓷砖的颜色是 蓝色 。
环中连续 k 块瓷砖的颜色假如是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。
请你返回 交替 组的数量。
留意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
示例 1：
输入：colors = , k = 3
输出：3
解释：
https://i-blog.csdnimg.cn/img_convert/695ddb2d717d063110eb32d2c0343449.png
交替组包括：
https://i-blog.csdnimg.cn/img_convert/1fe2d1bc1c8a30b2f3abb30acf53e3fc.pnghttps://i-blog.csdnimg.cn/img_convert/e84d27469b757cd89a5fa400bda7b690.pnghttps://i-blog.csdnimg.cn/img_convert/26e0f0811195a93127cc15d68c6d11cd.png
示例 2：
输入：colors = , k = 6
输出：2
解释：
https://i-blog.csdnimg.cn/img_convert/c0ce747f81f6147c763c6b3c328cffe2.png
交替组包括：
https://i-blog.csdnimg.cn/img_convert/630f03d1803c3bd6073bf8b4580f326c.pnghttps://i-blog.csdnimg.cn/img_convert/45efeba776586072eec3ed693d371c42.png
示例 3：
输入：colors = , k = 4
输出：0
解释：
https://i-blog.csdnimg.cn/img_convert/6e01ee27e20f88263a841e364f25c340.png
提示：
[*]3 <= colors.length <= 105
[*]0 <= colors <= 1
[*]3 <= k <= colors.length
解题方法：滑动窗口
利用一个大小为k的“窗口”，统计窗口中“相邻两个元素不相同”的个数。
从 0 0 0到 l e n ( c o l o r s ) − 1 len(colors) - 1 len(colors)−1遍历“窗口”的出发点，每次出发点向后移动一位，终点也向后移动一位（记得对 l e n ( c o l o r s ) len(colors) len(colors)取模）。
窗口每移动一次，就依据新加入窗口的“相邻元素对”和刚移出窗口的“相邻元素对”更新窗口中“相邻两个元素不相同”的个数。
每次窗口中“相邻两个元素不相同”的个数若为 k − 1 k - 1 k−1，则说明是一个符合要求的窗口，答案数量加一。
[*]时间复杂度 O ( l e n ( c o l o r s ) ) O(len(colors)) O(len(colors))
[*]空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
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 != colors) {
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;
}
return ans;
}
};
Python
from typing import List
class Solution:
def numberOfAlternatingGroups(self, colors: List, k: int) -> int:
ans = 0
cntDiff = sum(colors != colors 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
return ans
Java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int ans = 0;
int cntDiff = 0;
for (int i = 1; i < k; i++) {
if (colors != colors) {
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) {
cntDiff--;
}
}
return ans;
}
}
Go
package main
func numberOfAlternatingGroups(colors []int, k int) (ans int) {
cntDiff := 0
for i := 1; i < k; i++ {
if colors != colors {
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 {
cntDiff--
}
}
return
}
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/144123453
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]