发表于 2024.08.10

• 交替组I由于只需求连续3块瓷砖的交替，做法很简单，直接枚举模拟判断colors[i] == colors[(i + 2) % n] and colors[i] != colors[(i + 1) % n]即可；

  交替组II将瓷砖组的数量泛化为任意数量k，则需要考虑双指针的方法：left指针指向当前组的起始位置，right指针指向当前组的下一个比较位置。如果colors[right] != colors[(right - 1) % n]，意味着交替继续，right指针继续向右移动；否则，left指针指向right(快速移动，left只往右移动一位该组还是不会交替的，直接跳到right即可)，right指针指向下一个位置。当right == (left + k) % n时，意味着找到了一个交替组，ans += 1。

  交替组I的做法：

  class Solution:
      def numberOfAlternatingGroups(self, colors: List[int]) -> int:
          ans = 0
          n = len(colors)
          for i in range(n):
              if colors[i] == colors[(i + 2) % n] and colors[i] != colors[(i + 1) % n]:
                  ans += 1
          return ans

  交替组II的做法：

  class Solution:
      def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
          ans = 0
          n = len(colors)
          left = 0
          right = 1
          while left < len(colors):
              while (left + k) % n != right:
                  if colors[right] == colors[(right - 1) % n]:
                      break
                  right = (right + 1) % n
              if (left + k) % n != right:
                  if right <= left:
                      break
                  left = right
                  right = (right + 1) % n
              else:
                  ans += 1
                  left += 1
          return ans

• LC 题目链接