石子游戏 IX

题目描述：

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。
假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 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 总会获胜。其中一种可能的游戏进行方式如下：

• 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
• 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
• 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
• 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
• 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
  Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜

思路:

s=0 的石子数量为偶数：此时等价于没有 s = 0s=0 的石子，我们只需要关心 s = 1s=1 和 s = 2s=2 即可：

s = 1s=1 的石子数量为 00： 这意味着 A 开始选择的只能是 s = 2s=2，此时交给 B 的局面为「x = 2x=2、剩余石子只有 s = 2s=2」，此时 B 只能选 s = 2s=2 的石子，由于 x = 2x=2 且选择的石子 s = 2s=2，因此交由回 A 的局面为「x = 1x=1，剩余是在只有 s = 2s=2」，因此游戏继续的话 A 必败，同时如果在该过程的任何时刻石子被取完，也是 B 直接获胜，即 A 仍为必败；

s = 2s=2 的石子数量为 00：分析同理，A 只能选 s = 1s=1，此时交给 B 的局面为「x = 1x=1、剩余石子只有 s = 1s=1」，此时 B 只能选 s = 1s=1 的石子，由于 x = 1x=1 且选择的石子 s = 1s=1，因此交由回 A 的局面为「x = 2x=2，剩余是在只有 s = 1s=1」，因此游戏继续的话 A 必败，同时如果在该过程的任何时刻石子被取完，也是 B 直接获胜，即 A 仍为必败；

s = 1s=1 和 s = 2s=2 的石子数量均不为 00：A 选数量不是最多的一类石子，B 下一回合只能选择相同类型的石子（或是无从选择导致失败），然后游戏继续，最终 B 会先进入「只能凑成 33 的倍数」的局面导致失败，即 A 必胜。

s = 0s=0 的石子数量为奇数：此时等价于有一次换手机会，该换手机会必然应用在「对必败局面进行转移」才有意义，因此只有 s = 1s=1 和 s = 2s=2 的石子数量差大于 22，A 的先手优势不会因为存在换手机会而被转移：

两者数量差不超过 22：此时 B 可以利用「对方凑成 33 的倍数必败」规则和「优先使用 s = 0s=0 石子」权利来进入确保自己为必胜态：

举个 🌰，当 s = 1s=1 和 s = 2s=2 的石子数量相等，虽然有 s = 0s=0 的石子，A 先手，但是 A 的首个回合必然不能选 s = 0s=0，否则马上失败结束，因此 A 只能选 s = 1s=1 或 s = 2s=2，此时 B直接选择 s = 0s=0 的石子，交由给 A 的局面 xx 没有发生改变，A 只能选择与首个回合相同的 ss 游戏才能继续，因此局面会变为「B 先手、s = 1s=1 和 s = 2s=2 的石子数量差为 22」，游戏继续，最终 A 会先遇到「只能凑成 33 的倍数」的局面，即 B 必胜。

两者数量差不超过 2：此时无论 A 选择数量较少或较多的 s，B 都在第二回合马上使用 s = 0 的石子进行换手，A 只能继续选与第一回合相同类型的的石子，游戏才能进行，最终 A 会先遇到「只能凑成 3 的倍数」或「石子被取完」的局面，即 B 必胜。

两者数量差超过 2 ：此时即使 A 只要确保第一次选择数量较多的 s，不管 B 是否使用「优先使用 s = 0s=0」的石子，A 都有足够次数数量多 ss 来抵消换手（或是在 B 放弃使用 s = 0s=0 之后马上使用），最终都是 B 最先遇到「只能凑成 33 的倍数」的局面，即 A 获胜。

代码:

func stoneGameIX(stones []int) bool {
    var mode_0,mode_1,mode_2 int
    for _,v := range stones{
        if v %3 == 0{
            mode_0 ++
        }
        if v %3 == 1{
            mode_1 ++
        }
        if v % 3 ==2 {
            mode_2 ++
        }

    }

    if mode_0 % 2 ==0{
        return mode_1>=1 && mode_2 >=1
    }else{
        return abs(mode_1-mode_2)>2
    }
    
}

func abs(a int)int {
    if a <0{
        return -a
    }else{
        return a
    }
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：8.9 MB, 在所有 Go 提交中击败了73.08%的用户