同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下:
给你一个字符串 currentState
,其中只含 '+'
和 '-'
。你和朋友轮流将 连续 的两个 "++"
反转成 "--"
。当一方无法进行有效的翻转时便意味着游戏结束,则另一方获胜。默认每个人都会采取最优策略。
请你写出一个函数来判定起始玩家 是否存在必胜的方案 :如果存在,返回 true
;否则,返回 false
。
示例 1:
"++"
示例 2:
输入:currentState = "+" 输出:false
提示:
1 <= currentState.length <= 60
currentState[i]
不是 '+'
就是 '-'
进阶:请推导你算法的时间复杂度。
方法一:状态压缩 + 记忆化搜索
方法二:Sprague-Grundy 定理
Sprague-Grundy 定理为游戏的每一个状态定义了一个 Sprague-Grundy 数(简称 SG 数),游戏状态的组合相当于 SG 数的异或运算。
Sprague-Grundy 定理的完整表述如下:
若一个游戏满足以下条件:
则游戏中的每个状态可以按如下规则赋予一个非负整数,称为 Sprague-Grundy 数,即 $SG(A)=mex{SG(B)|A->B}$。(式中 $A$, $B$ 代表状态,代表 $A$ 状态经一步行动可以到达 $B$ 状态,而 $mex$ 表示一个集合所不包含的最小非负整数)
SG 数有如下性质:
时间复杂度 $O(n^2)$。
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)
class Solution:
def canWin(self, currentState: str) -> bool:
def win(i):
if sg[i] != -1:
return sg[i]
vis = [False] * n
for j in range(i - 1):
vis[win(j) ^ win(i - j - 2)] = True
for j in range(n):
if not vis[j]:
sg[i] = j
return j
return 0
n = len(currentState)
sg = [-1] * (n + 1)
sg[0] = sg[1] = 0
ans = i = 0
while i < n:
j = i
while j < n and currentState[j] == '+':
j += 1
ans ^= win(j - i)
i = j + 1
return ans > 0
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;
}
}
class Solution {
private int n;
private int[] sg;
public boolean canWin(String currentState) {
n = currentState.length();
sg = new int[n + 1];
Arrays.fill(sg, -1);
int i = 0;
int ans = 0;
while (i < n) {
int j = i;
while (j < n && currentState.charAt(j) == '+') {
++j;
}
ans ^= win(j - i);
i = j + 1;
}
return ans > 0;
}
private int win(int i) {
if (sg[i] != -1) {
return sg[i];
}
boolean[] vis = new boolean[n];
for (int j = 0; j < i - 1; ++j) {
vis[win(j) ^ win(i - j - 2)] = true;
}
for (int j = 0; j < n; ++j) {
if (!vis[j]) {
sg[i] = j;
return j;
}
}
return 0;
}
}
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;
}
};
class Solution {
public:
bool canWin(string currentState) {
int n = currentState.size();
vector<int> sg(n + 1, -1);
sg[0] = 0, sg[1] = 0;
function<int(int)> win = [&](int i) {
if (sg[i] != -1) return sg[i];
vector<bool> vis(n);
for (int j = 0; j < i - 1; ++j) vis[win(j) ^ win(i - j - 2)] = true;
for (int j = 0; j < n; ++j)
if (!vis[j]) return sg[i] = j;
return 0;
};
int ans = 0, i = 0;
while (i < n) {
int j = i;
while (j < n && currentState[j] == '+') ++j;
ans ^= win(j - i);
i = j + 1;
}
return ans > 0;
}
};
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)
}
func canWin(currentState string) bool {
n := len(currentState)
sg := make([]int, n+1)
for i := range sg {
sg[i] = -1
}
var win func(i int) int
win = func(i int) int {
if sg[i] != -1 {
return sg[i]
}
vis := make([]bool, n)
for j := 0; j < i-1; j++ {
vis[win(j)^win(i-j-2)] = true
}
for j := 0; j < n; j++ {
if !vis[j] {
sg[i] = j
return j
}
}
return 0
}
ans, i := 0, 0
for i < n {
j := i
for j < n && currentState[j] == '+' {
j++
}
ans ^= win(j - i)
i = j + 1
}
return ans > 0
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。