原文链接: https://leetcode-cn.com/problems/stone-game-ix

英文原文

Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).

Assuming both players play optimally, return true if Alice wins and false if Bob wins.

 

Example 1:

Input: stones = [2,1]
Output: true
Explanation: The game will be played as follows:
- Turn 1: Alice can remove either stone.
- Turn 2: Bob removes the remaining stone. 
The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.

Example 2:

Input: stones = [2]
Output: false
Explanation: Alice will remove the only stone, and the sum of the values on the removed stones is 2. 
Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.

Example 3:

Input: stones = [5,1,2,4,3]
Output: false
Explanation: Bob will always win. One possible way for Bob to win is shown below:
- Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1.
- Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4.
- Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8.
- Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10.
- Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15.
Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.

 

Constraints:

• 1 <= stones.length <= 105
• 1 <= stones[i] <= 104

中文题目

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 获胜。

 

提示：

• 1 <= stones.length <= 105
• 1 <= stones[i] <= 104

通过代码

高赞题解

由于我们只关心总和能否被 $3$ 整除，我们可以将 $\textit{stones}$ 按照模 $3$ 的结果分为 $3$ 组，即 $0$、$1$ 和 $2$。

根据题意，第一回合不能移除 $0$，否则直接输掉游戏，因此第一回合只能移除 $1$ 或者 $2$。我们可以枚举这两种情况，如果其中一种可以让 Alice 获胜就返回 $\texttt{true}$，否则返回 $\texttt{false}$。

下面以第一回合移除 $1$ 来说明。在不考虑移除 $0$ 的前提下，后面的移除由于要满足总和不能被 $3$ 整除，因此移除的石子是固定的，整体构成一个 $112121212\dots$ 循环的序列。

对于 $0$，由于移除之后不会改变总和模 $3$ 的结果，因此不会改变后续 $1$ 和 $2$ 的移除顺序，所以我们可以在序列的任意非开头位置插入 $0$。

两人为了不让自己输掉，必然会按照上述序列进行，直到没有石子，或某一方只能移除导致总和被 $3$ 整除的石子时分出胜负。因此我们需要求出让总和不能被 $3$ 整除的最大的回合数，这相当于 $112121212\dots$ 序列的最长长度，加上 $0$ 的个数。

若该回合数为奇数，且还有剩余石子，那么下一回合要轮到 Bob 移除石子，且他只能移除一枚让总和被 $3$ 整除的石子，于是 Alice 获胜；否则 Bob 获胜。

对于第一回合移除 $2$ 的情况，同样会构成一个 $221212121\dots$ 循环的序列，做法同上。

func check(c [3]int) bool {
	if c[1] == 0 {
		return false
	}
	c[1]-- // 开头为 1
	turn := 1 + min(c[1], c[2])*2 + c[0] // 计算回合数
	if c[1] > c[2] { // 序列末尾可以再加个 1
		turn++
		c[1]--
	}
	return turn%2 == 1 && c[1] != c[2] // 回合数为奇数，且还有剩余石子
}

func stoneGameIX(stones []int) bool {
	c := [3]int{}
	for _, v := range stones {
		c[v%3]++
	}
	return check(c) || check([3]int{c[0], c[2], c[1]}) // 枚举第一回合移除的是 1 还是 2
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

下面来简化这份代码的判断逻辑。

注意到对于回合数，我们只需考虑其奇偶性，因此可以去掉恒为偶数的 min(c[1], c[2])*2。然后我们按照 $c[0]$ 的奇偶性分类讨论：

• 若 $c[0]$ 为偶数，要使回合数为奇数，c[1] > c[2] 必须不成立，我们可以选择 $c[1]$ 和 $c[2]$ 中的较小值当作第一回合移除的石子，这样做除了让 c[1] > c[2] 不成立外，由于 c[1]-- 的缘故，还可以使 c[1] != c[2] 成立。因此在 $c[0]$ 为偶数的情况下，需要满足 $\min(c[1],c[2])>0$，即 $c[1]>0$ 且 $c[2]>0$ 时 Alice 才可以获胜。
• 若 $c[0]$ 为奇数，要使回合数为奇数，c[1] > c[2] 必须成立。在执行了两次 c[1]-- 后，由于要满足最后的 c[1] != c[2]，相当于在初始时满足 c[1] - 2 > c[2]。因此在 $c[0]$ 为奇数的情况下，需要满足 $c[1] - 2 > c[2]$ 或 $c[2] - 2 > c[1]$ 时 Alice 才可以获胜。

func stoneGameIX(stones []int) bool {
	c := [3]int{}
	for _, v := range stones {
		c[v%3]++
	}
	if c[0]%2 == 0 {
		return c[1] > 0 && c[2] > 0 // min(c[1], c[2]) > 0
	}
	return c[1]-2 > c[2] || c[2]-2 > c[1]
}

统计信息

通过次数	提交次数	AC比率
2264	9646	23.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言