資料結構
網路
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 次瀏覽
廣告