Medium

题目描述

有 n 个棋子排成一行，每个棋子要么是 ‘A’ 色，要么是 ‘B’ 色。给你一个长度为 n 的字符串 colors，其中 colors[i] 是第 i 个棋子的颜色。

Alice 和 Bob 在玩一个游戏，他们轮流从这一行中移除棋子。在这个游戏中，Alice 先手。

  • Alice 只能移除颜色为 ‘A’ 的棋子，且该棋子的两个相邻棋子也都是 ‘A’ 色。她不能移除颜色为 ‘B’ 的棋子。
  • Bob 只能移除颜色为 ‘B’ 的棋子，且该棋子的两个相邻棋子也都是 ‘B’ 色。他不能移除颜色为 ‘A’ 的棋子。
  • Alice 和 Bob 都不能移除边缘的棋子。
  • 如果某个玩家在轮到自己时无法移动，该玩家输掉游戏，另一个玩家获胜。

假设 Alice 和 Bob 都以最佳策略游戏，如果 Alice 获胜返回 true，如果 Bob 获胜返回 false。

示例 1:

输入: colors = "AAABABB"
输出: true
解释:
AAABABB -> AABABB
Alice 先手。
她移除左边第二个 'A'，因为那是唯一一个两个相邻棋子都是 'A' 的 'A' 棋子。

现在轮到 Bob。
Bob 无法移动，因为没有两个相邻棋子都是 'B' 的 'B' 棋子。
因此，Alice 获胜，返回 true。

示例 2:

输入: colors = "AA"
输出: false
解释:
Alice 先手。
只有两个 'A'，且都在边缘，所以她无法移动。
因此，Bob 获胜，返回 false。

示例 3:

输入: colors = "ABBBBBBBAAA"
输出: false

提示:

  • 1 <= colors.length <= 10^5
  • colors 只包含字母 ‘A’ 和 ‘B’

解题思路

这是一个博弈论问题，关键观察是：每个玩家能执行的移动次数是独立的，不会相互影响。

核心思路

  1. 移动规则分析：Alice 只能移除连续 A 序列中间的 ‘A’，Bob 只能移除连续 B 序列中间的 ‘B’
  2. 移动次数计算：对于长度为 k 的连续相同颜色序列，可以移除 max(0, k-2) 个棋子
  3. 胜负判断：Alice 的总移动次数 > Bob 的总移动次数时，Alice 胜利

解法思路

遍历字符串，统计每个连续相同颜色段的长度：

  • 连续的 ‘A’ 段长度为 k，Alice 可以移动 k-2 次（k≥3时）
  • 连续的 ‘B’ 段长度为 k，Bob 可以移动 k-2 次（k≥3时）

最后比较双方总移动次数即可。

时间复杂度：O(n)，遍历一次字符串 空间复杂度：O(1)，只使用常数额外空间

这种贪心策略是最优的，因为每次移动都会减少可移动的棋子数量，且双方移动互不干扰。

代码实现

class Solution {
public:
    bool winnerOfGame(string colors) {
        int aliceMoves = 0, bobMoves = 0;
        int n = colors.length();
        
        for (int i = 0; i < n; ) {
            char color = colors[i];
            int count = 0;
            
            // 统计连续相同颜色的长度
            while (i < n && colors[i] == color) {
                count++;
                i++;
            }
            
            // 计算可移除的棋子数量
            if (count >= 3) {
                if (color == 'A') {
                    aliceMoves += count - 2;
                } else {
                    bobMoves += count - 2;
                }
            }
        }
        
        return aliceMoves > bobMoves;
    }
};

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice_moves = bob_moves = 0
        n = len(colors)
        i = 0
        
        while i < n:
            color = colors[i]
            count = 0
            
            # 统计连续相同颜色的长度
            while i < n and colors[i] == color:
                count += 1
                i += 1
            
            # 计算可移除的棋子数量
            if count >= 3:
                if color == 'A':
                    alice_moves += count - 2
                else:
                    bob_moves += count - 2
        
        return alice_moves > bob_moves

public class Solution {
    public bool WinnerOfGame(string colors) {
        int aliceMoves = 0, bobMoves = 0;
        int n = colors.Length;
        
        for (int i = 0; i < n; ) {
            char color = colors[i];
            int count = 0;
            
            // 统计连续相同颜色的长度
            while (i < n && colors[i] == color) {
                count++;
                i++;
            }
            
            // 计算可移除的棋子数量
            if (count >= 3) {
                if (color == 'A') {
                    aliceMoves += count - 2;
                } else {
                    bobMoves += count - 2;
                }
            }
        }
        
        return aliceMoves > bobMoves;
    }
}

/**
 * @param {string} colors
 * @return {boolean}
 */
var winnerOfGame = function(colors) {
    let aliceMoves = 0, bobMoves = 0;
    const n = colors.length;
    
    for (let i = 0; i < n; ) {
        const color = colors[i];
        let count = 0;
        
        // 统计连续相同颜色的长度
        while (i < n && colors[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

相关题目