题目描述
你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：
给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将 连续 的两个 "++" 反转成 "--" 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。
请你写出一个函数来判定起始玩家 是否存在必胜的方案 ：如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：currentState = "++++"
输出：true
解释：起始玩家可将中间的 "++" 翻转变为 "+--+" 从而得胜。
示例 2：
输入：currentState = "+"
输出：false
提示：
1 <= currentState.length <= 60currentState[i] 不是 '+' 就是 '-'- 不能有超过 20 个连续的
'+'。
进阶：请推导你算法的时间复杂度。
解法
方法一：状态压缩 + 记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def canWin(self, currentState: str) -> bool:
@cache
def dfs(mask):
for i in range(n - 1):
if (mask & (1 << i)) == 0 or (mask & (1 << (i + 1)) == 0):
continue
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))):
continue
return True
return False
mask, n = 0, len(currentState)
for i, c in enumerate(currentState):
if c == '+':
mask |= 1 << i
return dfs(mask)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
private int n;
private Map<Long, Boolean> memo = new HashMap<>();
public boolean canWin(String currentState) {
long mask = 0;
n = currentState.length();
for (int i = 0; i < n; ++i) {
if (currentState.charAt(i) == '+') {
mask |= 1 << i;
}
}
return dfs(mask);
}
private boolean dfs(long mask) {
if (memo.containsKey(mask)) {
return memo.get(mask);
}
for (int i = 0; i < n - 1; ++i) {
if ((mask & (1 << i)) == 0 || (mask & (1 << (i + 1))) == 0) {
continue;
}
if (dfs(mask ^ (1 << i) ^ (1 << (i + 1)))) {
continue;
}
memo.put(mask, true);
return true;
}
memo.put(mask, false);
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | using ll = long long;
class Solution {
public:
int n;
unordered_map<ll, bool> memo;
bool canWin(string currentState) {
n = currentState.size();
ll mask = 0;
for (int i = 0; i < n; ++i)
if (currentState[i] == '+') mask |= 1ll << i;
return dfs(mask);
}
bool dfs(ll mask) {
if (memo.count(mask)) return memo[mask];
for (int i = 0; i < n - 1; ++i) {
if ((mask & (1ll << i)) == 0 || (mask & (1ll << (i + 1))) == 0) continue;
if (dfs(mask ^ (1ll << i) ^ (1ll << (i + 1)))) continue;
memo[mask] = true;
return true;
}
memo[mask] = false;
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func canWin(currentState string) bool {
n := len(currentState)
memo := map[int]bool{}
mask := 0
for i, c := range currentState {
if c == '+' {
mask |= 1 << i
}
}
var dfs func(int) bool
dfs = func(mask int) bool {
if v, ok := memo[mask]; ok {
return v
}
for i := 0; i < n-1; i++ {
if (mask&(1<<i)) == 0 || (mask&(1<<(i+1))) == 0 {
continue
}
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))) {
continue
}
memo[mask] = true
return true
}
memo[mask] = false
return false
}
return dfs(mask)
}
|
方法二：Sprague-Grundy 定理
Sprague-Grundy 定理为游戏的每一个状态定义了一个 Sprague-Grundy 数（简称 SG 数），游戏状态的组合相当于 SG 数的异或运算。
Sprague-Grundy 定理的完整表述如下：
若一个游戏满足以下条件：
- 双人、回合制
- 信息完全公开
- 无随机因素
- 必然在有限步内结束，且每步的走法数有限
- 没有平局
- 双方可采取的行动及胜利目标都相同
- 这个胜利目标是自己亲手达成终局状态，或者说走最后一步者为胜（normal play）
则游戏中的每个状态可以按如下规则赋予一个非负整数，称为 Sprague-Grundy 数，即 \(SG(A)=mex\{SG(B)|A->B\}\)。（式中 \(A\), \(B\) 代表状态，代表 \(A\) 状态经一步行动可以到达 \(B\) 状态，而 \(mex\) 表示一个集合所不包含的最小非负整数）
SG 数有如下性质：
- SG 数为 0 的状态，后手必胜；SG 数为正的状态，先手必胜；
- 若一个母状态可以拆分成多个相互独立的子状态，则母状态的 SG 数等于各个子状态的 SG 数的异或。
参考资料：Sprague-Grundy 定理是怎么想出来的
时间复杂度 \(O(n^2)\)。