游戏规则如下：
给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将 连续 的两个 "++" 反转成 "--" 。你是先手玩家。
当一方无法进行翻转时便意味着游戏结束，另一方获胜。默认每个人都会采取最优策略。
请你判定你自己是否存在必胜的方案 ：如果存在，返回 true ；否则，返回 false 。
输入：currentState = "++++"
输出：true
解释：你作为先手玩家，可将中间的 "++" 翻转变为 "+--+" ，从而获胜。数据范围 ： 1 <= currentState.length <= 60
这题我想了半天，想到一种 可能的 动态规划的办法，但是苦于技术菜，没法完整实现自己的想法（也可能是因为我的想法本身就是错误的），也没法证明它是否正确。
所以想请教各位。😂😂
我的想法是这样的：如果一段连续的 加号数量 是确定的，那么这一段的结果（谁获胜）也是确定的。
比如，我已知的初始情况是 ： ++ 、 +++ 、 ++++ 。这些情况都一定是当前先手玩家获胜。
如果是连续4个以上的加号，可以每次减2（因为每次会翻转两个），最终 这个连续长度 会变为某个 已知结果的长度 。
此外，在每次减2的过程中，还要用一个布尔变量来维护先后手玩家的顺序（不断取反）。
以上就是我的想法，我也给它写了一些代码，但我感觉自己既不能完整实现这个想法的逻辑，也不能证明它的正确性，全凭直觉。
Java
public class Solution {
public boolean canWin(String currentState) {
if (currentState.length() == 1) {
return false;
}
// 以 '-' 作为分隔符，可以将字符串分为一段段连续的 '+'
// len[i] -> 第i段连续的 '+' 的长度
int[] len = new int[61]; // 61是由于数据范围 1<=currentState.length<=60，所以直接开辟了一个61的
int left = 0, pointer = 0;
for (int right = 0, N = currentState.length(); right < N; right++) {
if (currentState.charAt(right) == '-') {
if (left < right) {
len[pointer++] = right - left + 1;
}
left = right + 1;
}
}
if (left == 0) {
// 整个字符串中不存在 '-' ，即：整个字符串是一个连续的 '+'
len[pointer++] = currentState.length();
}
// 维护当前先后手玩家的关系。如果当前回合是后手玩家的，那么记为 false
boolean reversed = false;
// dp[i] -> 先手玩家能否在长度为i的连续'+' 中必胜
Boolean[] dp = new Boolean[61];
// change[i] -> 在翻转完毕长度为i的连续段之后，是否会导致先后手的顺序互换
// 例如："++++" 则先手翻转一次，然后不能再翻转，这会导致下一轮的先手是当前的后手玩家
boolean[] change = new boolean[61];
dp[1] = false;
dp[2] = dp[3] = dp[4] = true;
change[2] = change[3] = change[4] = true;
// 处理每一段连续的 '+'
for (int i = 0; i < pointer; i++) {
if (dp[len[i]] == null) {
// 当前长度谁赢是不确定的。但是可以通过不断减2，直到变为某个确定的长度，由此推出答案
int length = len[i];
while (length > 4 && dp[length] == null) {
length -= 2;
reversed = !reversed;
}
dp[len[i]] = !reversed && dp[length - 2];
change[len[i]] = change[length - 2];
} else {
reversed = change[len[i]] && !reversed;
}
}
return !reversed && dp[len[pointer - 1]];
}
}评论 (14)
