翻转游戏 II
难度:
标签:
题目描述
代码结果
运行时间: 31 ms, 内存: 16.1 MB
/*
* 翻转游戏 II 题解 - Java Stream
* 解题思路：
* 1. 遍历字符串，找到所有可以翻转的 "++"。
* 2. 对每一种可能的翻转情况，递归判断翻转后的状态。
* 3. 如果翻转后所有的可能状态中有一种是对手必输的状态，则先手玩家必胜。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean canWin(String currentState) {
if (currentState == null || currentState.length() < 2) {
return false;
}
return IntStream.range(0, currentState.length() - 1)
.filter(i -> currentState.startsWith("++", i))
.mapToObj(i -> currentState.substring(0, i) + "--" + currentState.substring(i + 2))
.anyMatch(nextState -> !canWin(nextState));
}
}解释
方法:
这个题解使用了博弈论中的 SG 定理。将初始的字符串 s 按照连续的 '+' 分割成多个子串，每个子串代表一个独立的游戏局面。对每个子串计算它的 SG 函数值，最后将所有 SG 函数值做异或操作，如果结果大于 0，则先手必胜，否则先手必败。
在计算单个子串的 SG 函数时，使用记忆化搜索 dfs(x)，其中 x 表示当前子串的长度。搜索过程中，枚举所有可能的分割方式，将分割后的两部分递归计算 SG 函数，并做异或操作，得到一个 SG 函数值的集合。最后，用 mex 函数找到最小的不属于这个集合的非负整数，作为当前状态的 SG 函数值。
时间复杂度:
O(n^3)
空间复杂度:
O(n)
代码细节讲解
🦆
SG定理是如何应用于解决这种翻转游戏问题的？能否进一步解释SG定理的基本原理和它在这个问题中的具体作用？
▷🦆
在实现记忆化搜索的`dfs`函数中，为什么选取长度小于2的子串SG函数值为0？这样的处理是否意味着长度小于2的子串没有有效的移动？
▷🦆
题解中提到的`mex`函数是如何确保找到最小的不被SG函数值集合包含的非负整数的？能否详细说明其工作原理？
▷🦆
在分割字符串时，为什么选择连续的'+'作为分割点？这种方法是否考虑了所有可能的游戏状态？
▷相关问题
Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合， 你作为先手 。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。
示例 2：
输入：n = 1 输出：true
示例 3：
输入：n = 2 输出：true
提示：
1 <= n <= 231 - 1
猜数字大小 II
我们正在玩一个猜数游戏，游戏规则如下：
- 我从
1到n之间选择一个数字。 - 你来猜我选了哪个数字。
- 如果你猜到正确的数字，就会 赢得游戏 。
- 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
- 每当你猜了数字
x并且猜错了的时候，你需要支付金额为x的现金。如果你花光了钱，就会 输掉游戏 。
给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。
示例 1：
输入：n = 10 输出：16 解释：制胜策略如下： - 数字范围是 [1,10] 。你先猜测数字为 7 。 - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $7 。 - 如果我的数字更大，则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。 - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $9 。 - 如果我的数字更大，那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16 。 - 如果我的数字更小，那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16 。 - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。 - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $3 。 - 如果我的数字更大，则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。 - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5 。 - 如果我的数字更大，那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。 - 如果我的数字更小，那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。 - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。 - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $1 。 - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11 。 在最糟糕的情况下，你需要支付 $16 。因此，你只需要 $16 就可以确保自己赢得游戏。
示例 2：
输入：n = 1 输出：0 解释：只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。
示例 3：
输入：n = 2 输出：1 解释：有两个可能的数字 1 和 2 。 - 你可以先猜 1 。 - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。 - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。 最糟糕的情况下，你需要支付 $1 。
提示：
1 <= n <= 200
我能赢吗
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
示例 1：
输入：maxChoosableInteger = 10, desiredTotal = 11 输出：false 解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
示例 2:
输入：maxChoosableInteger = 10, desiredTotal = 0 输出：true
示例 3:
输入：maxChoosableInteger = 10, desiredTotal = 1 输出：true
提示:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300