PeterQwQ
0%

Leetcode 3208 交替组 II

发表于

给你一个整数数组 colors 和一个整数 k ， colors 表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

  • colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
  • colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。注意 ，由于 colors 表示一个 环 ， 第一块 瓷砖和 最后一块 瓷砖是相邻的。

由于整体上是一个环，所以需要拓展到 n+k-2 的长度，然后遍历，如果当前颜色与下一个颜色不同，那么计数器加一，如果计数器等于 k，那么结果加一，然后计数器减一，继续遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        cnt, res = 1, 0
        for i in range(n+k-2):
            if colors[i%n] != colors[(i+1)%n]:
                cnt += 1
                if cnt == k:
                    res += 1
                    cnt -= 1
                    continue
            else:
                cnt = 1
        return res