数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学C++ 版 2 人反转游戏
假设有两位玩家正在玩反转游戏。这里有一个仅包含以下两个字符的字符串：+ 和 -，玩家 1 和玩家 2 轮流将两个连续的“++”反转为“--”。当一名玩家无法再出招时游戏结束，另一名玩家将获胜。我们必须定义一个函数来检查起始玩家是否可以保证获胜。
因此，如果输入为 s = "++++"，则输出将为 true，因为起始玩家可以通过将中间的“++”反转为“+-+”来保证获胜。
要解决此问题，我们将遵循以下步骤 -
定义一个映射 memo
定义一个函数 solve()，它将带入 s，
如果 s 在 memo 中，则 -
返回 memo[s]
possible := false
n := s 的大小
初始化 i := 0 时，当 i < n - 1 时，更新（将 i + 1），执行 -
如果 s[i] 与 '+' 相同且 s[i + 1] 与 '+' 相同，则 -
s[i] := '-', s[i + 1] := '-'
possible := possible 或 solve(s) 的反转
s[i] := '+', s[i + 1] := '+'
如果 possible 非零，则 -
返回 memo[s] := possible
返回 memo[s] := possible
在主方法中执行以下操作 -
返回解决 (s)
示例
让我们参考以下实现来获得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
unordered_map <string, bool> memo;
bool solve(string s){
if (memo.count(s))
return memo[s];
bool possible = false;
int n = s.size();
for (int i = 0; i < n - 1; i++) {
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = '-';
s[i + 1] = '-';
possible |= !solve(s);
s[i] = '+';
s[i + 1] = '+';
if (possible)
return memo[s] = possible;
}
}
return memo[s] = possible;
}
bool canWin(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.canWin("++++"));
}输入
"++++"
输出
1
更新于: 18-Nov-2020
249 次浏览
广告