Medium

题目描述

Alice 和 Bob 继续他们的石子游戏。现在有一排 n 个石子，每个石子都有一个关联的值。给你一个整数数组 stones，其中 stones[i] 是第 i 个石子的值。

Alice 和 Bob 轮流进行游戏，Alice 先手。在每一轮中，玩家可以从 stones 中移除任意一个石子。如果移除石子后，所有已移除石子的值的总和可被 3 整除，则移除石子的玩家败北。如果没有剩余的石子了（即使轮到 Alice），Bob 自动获胜。

假设两个玩家都采用最优策略，如果 Alice 获胜返回 true，否则返回 false。

示例 1：

输入：stones = [2,1]
输出：true
解释：游戏进行如下：
- 第 1 轮：Alice 可以移除任意一个石子。
- 第 2 轮：Bob 移除剩下的石子。
移除石子的值总和是 1 + 2 = 3，可被 3 整除。因此，Bob 败北，Alice 获胜。

示例 2：

输入：stones = [2]
输出：false
解释：Alice 将移除唯一的石子，移除石子的值总和是 2。
由于所有石子都被移除且值的总和不能被 3 整除，Bob 获胜。

示例 3：

输入：stones = [5,1,2,4,3]
输出：false
解释：Bob 总是获胜。Bob 获胜的一种可能方式如下所示：
- 第 1 轮：Alice 可以移除第二个石子，值为 1。移除石子的总和 = 1。
- 第 2 轮：Bob 移除第五个石子，值为 3。移除石子的总和 = 1 + 3 = 4。
- 第 3 轮：Alice 移除第四个石子，值为 4。移除石子的总和 = 1 + 3 + 4 = 8。
- 第 4 轮：Bob 移除第三个石子，值为 2。移除石子的总和 = 1 + 3 + 4 + 2 = 10。
- 第 5 轮：Alice 移除第一个石子，值为 5。移除石子的总和 = 1 + 3 + 4 + 2 + 5 = 15。
Alice 败北，因为移除石子的总和（15）可被 3 整除。Bob 获胜。

提示：

  • 1 <= stones.length <= 10^5
  • 1 <= stones[i] <= 10^4

解题思路

这道题是一道博弈论问题，需要分析在最优策略下 Alice 能否获胜。

首先分析关键性质：石子的值对 3 取模只有三种情况：0、1、2。我们统计这三种石子的数量，记为 count0、count1、count2。

核心观察：

  1. 值为 0 的石子不会改变总和模 3 的结果，但会改变游戏轮次
  2. 值为 1 或 2 的石子会改变总和模 3 的结果
  3. Alice 要想获胜，必须让 Bob 在某轮后总和变为 3 的倍数

策略分析：

  • Alice 首轮必须选择值为 1 或 2 的石子（选 0 会直接让 Bob 获得优势）
  • 如果 Alice 首轮选 1，那么接下来的序列应该是 1→1→1… 或 1→2→2→1→1… 的模式
  • 如果 Alice 首轮选 2，那么接下来的序列应该是 2→2→2… 或 2→1→1→2→2… 的模式

我们需要模拟两种情况：Alice 首选 1 和 Alice 首选 2，看是否至少有一种能让 Alice 获胜。

关键是要考虑：

  1. 足够的石子数量来维持游戏
  2. 0 石子的影响（可以用来调整轮次）
  3. 避免 Alice 被迫选择导致总和为 3 倍数的石子

代码实现

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        vector<int> count(3, 0);
        for (int stone : stones) {
            count[stone % 3]++;
        }
        
        return canAliceWin(count, 1) || canAliceWin(count, 2);
    }
    
private:
    bool canAliceWin(vector<int>& count, int start) {
        if (count[start] == 0) return false;
        
        count[start]--;
        int alice = 1; // Alice's turn
        int sum = start;
        
        while (true) {
            if (alice) {
                if (sum % 3 == 1) {
                    if (count[1] > 0) {
                        count[1]--;
                        sum += 1;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        count[start]++; // restore
                        return false;
                    }
                } else { // sum % 3 == 2
                    if (count[2] > 0) {
                        count[2]--;
                        sum += 2;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        count[start]++; // restore
                        return false;
                    }
                }
            } else {
                if (sum % 3 == 1) {
                    if (count[2] > 0) {
                        count[2]--;
                        sum += 2;
                        count[start]++; // restore
                        return true;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        count[start]++; // restore
                        return false;
                    }
                } else { // sum % 3 == 2
                    if (count[1] > 0) {
                        count[1]--;
                        sum += 1;
                        count[start]++; // restore
                        return true;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        count[start]++; // restore
                        return false;
                    }
                }
            }
            alice = 1 - alice;
        }
    }
};

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        count = [0, 0, 0]
        for stone in stones:
            count[stone % 3] += 1
        
        return self.canAliceWin(count[:], 1) or self.canAliceWin(count[:], 2)
    
    def canAliceWin(self, count, start):
        if count[start] == 0:
            return False
        
        count[start] -= 1
        alice = True
        sum_mod = start
        
        while True:
            if alice:
                if sum_mod == 1:
                    if count[1] > 0:
                        count[1] -= 1
                        sum_mod = (sum_mod + 1) % 3
                    elif count[0] > 0:
                        count[0] -= 1
                    else:
                        return False
                else:  # sum_mod == 2
                    if count[2] > 0:
                        count[2] -= 1
                        sum_mod = (sum_mod + 2) % 3
                    elif count[0] > 0:
                        count[0] -= 1
                    else:
                        return False
            else:
                if sum_mod == 1:
                    if count[2] > 0:
                        return True
                    elif count[0] > 0:
                        count[0] -= 1
                    else:
                        return False
                else:  # sum_mod == 2
                    if count[1] > 0:
                        return True
                    elif count[0] > 0:
                        count[0] -= 1
                    else:
                        return False
            alice = not alice

public class Solution {
    public bool StoneGameIX(int[] stones) {
        int[] count = new int[3];
        foreach (int stone in stones) {
            count[stone % 3]++;
        }
        
        return CanAliceWin((int[])count.Clone(), 1) || CanAliceWin((int[])count.Clone(), 2);
    }
    
    private bool CanAliceWin(int[] count, int start) {
        if (count[start] == 0) return false;
        
        count[start]--;
        bool alice = true;
        int sumMod = start;
        
        while (true) {
            if (alice) {
                if (sumMod == 1) {
                    if (count[1] > 0) {
                        count[1]--;
                        sumMod = (sumMod + 1) % 3;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        return false;
                    }
                } else {
                    if (count[2] > 0) {
                        count[2]--;
                        sumMod = (sumMod + 2) % 3;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        return false;
                    }
                }
            } else {
                if (sumMod == 1) {
                    if (count[2] > 0) {
                        return true;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        return false;
                    }
                } else {
                    if (count[1] > 0) {
                        return true;
                    } else if (count[0] > 0) {
                        count[0]--;
                    } else {
                        return false;
                    }
                }
            }
            alice = !alice;
        }
    }
}

var stoneGameIX = function(stones) {
    const count = [0, 0, 0];
    for (const stone of stones) {
        count[stone % 3]++;
    }
    
    return canAliceWin([...count], 1) || canAliceWin([...count], 2);
};

function canAliceWin(count, start) {
    if (count[start]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
统计石子数量O(n)O(1)
模拟游戏过程O(n)O(1)
总计O(n)O(1)

其中 n 是石子数组的长度。空间复杂度为常数级别，因为只需要存储三种类型石子的计数。

相关题目