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 = [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 <= 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++

1. class Solution {
2. public:
3.     int numberOfAlternatingGroups(vector<int>& colors, int k) {
4.         int ans = 0;
5.         int cntDiff = 0;
6.         for (int i = 1; i < k; i++) {
7.             if (colors[i] != colors[i - 1]) {
8.                 cntDiff++;
9.             }
10.         }
11.         for (int i = 0; i < colors.size(); i++) {
12.             ans += cntDiff == k - 1;
13.             cntDiff += colors[(i + k) % colors.size()] != colors[(i + k - 1) % colors.size()];
14.             cntDiff -= colors[(i + 1) % colors.size()] != colors[i];
15.         }
16.         return ans;
17.     }
18. };

复制代码

Python

1. from typing import List
3. class Solution:
4.     def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
5.         ans = 0
6.         cntDiff = sum(colors[i] != colors[i - 1] for i in range(1, k))
7.         for i in range(len(colors)):
8.             ans += cntDiff == k - 1
9.             cntDiff += colors[(i + k) % len(colors)] != colors[(i + k - 1) % len(colors)]
10.             cntDiff -= colors[(i + 1) % len(colors)] != colors[i]
11.         return ans

复制代码

Java

1. class Solution {
2.     public int numberOfAlternatingGroups(int[] colors, int k) {
3.         int ans = 0;
4.         int cntDiff = 0;
5.         for (int i = 1; i < k; i++) {
6.             if (colors[i] != colors[i - 1]) {
7.                 cntDiff++;
8.             }
9.         }
10.         for (int i = 0; i < colors.length; i++) {
11.             if (cntDiff == k - 1) {
12.                 ans++;
13.             }
14.             if (colors[(i + k) % colors.length] != colors[(i + k - 1) % colors.length]) {
15.                 cntDiff++;
16.             }
17.             if (colors[(i + 1) % colors.length] != colors[i]) {
18.                 cntDiff--;
19.             }
20.         }
21.         return ans;
22.     }
23. }

复制代码

Go

1. package main
3. func numberOfAlternatingGroups(colors []int, k int) (ans int) {
4.     cntDiff := 0
5.     for i := 1; i < k; i++ {
6.         if colors[i] != colors[i - 1] {
7.             cntDiff++
8.         }
9.     }
10.     for i := range colors {
11.         if cntDiff == k - 1 {
12.             ans++
13.         }
14.         if colors[(i + k) % len(colors)] != colors[(i + k - 1) % len(colors)] {
15.             cntDiff++
16.         }
17.         if colors[(i + 1) % len(colors)] != colors[i] {
18.             cntDiff--
19.         }
20.     }
21.     return
22. }

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  Tisfy：https://letmefly.blog.csdn.net/article/details/144123453

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。