image.png

思路：贪心 + 滑动窗口

  • 此题比较难读懂，但是需要明确一个基本的思路：无论Alice怎么操作，她都无法影响Bob的操作，换句话说，Bob的最大操作次数，不受Alice影响，反之亦然。
  • 所以说，如果一方想要获胜，不用关注自己如何干扰对手（因为没办法干扰），只需保证自己的操作次数尽可能多（贪心）
  • 如何保证自己的操作尽可能多呢？每次只删除窗口大小为3的AAA序列里中间的那个A即可，这样可以保证自己的操作周期尽可能长。
  • 所以，只要统计窗口大小为3的序列的数量即可，谁多谁就赢。

    代码：

    1. class Solution:
    2.   # 贪心算法 + 滑动窗口
    3.   def winnerOfGame(self, colors: str) -> bool:
    4.       window_size = 3
    5.       len_colors = len(colors)
    6.       cnt_colors = collections.defaultdict(int)
    7.       for begin_pos in range(len_colors - window_size + 1):
    8.           if colors[begin_pos] == colors[begin_pos + 1] and colors[begin_pos] == colors[begin_pos + 2]:
    9.               cnt_colors[colors[begin_pos]] += 1
    10.           else:
    11.               pass
    12.       return cnt_colors['A'] > cnt_colors['B']