สมมติว่ามีผู้เล่นสองคนที่กำลังเล่นเกมพลิก ในที่นี้ เรามีสตริงที่มีอักขระสองตัวนี้เท่านั้น:+ และ -, player1 และ player2 ผลัดกันพลิก "++" สองตัวติดต่อกันเป็น "--" เกมจะจบลงเมื่อผู้เล่นคนหนึ่งไม่สามารถเคลื่อนไหวได้อีกต่อไป ดังนั้นอีกคนหนึ่งจะเป็นผู้ชนะ เราต้องกำหนดฟังก์ชั่นเพื่อตรวจสอบว่าผู้เล่นเริ่มต้นสามารถรับประกันชัยชนะได้หรือไม่
ดังนั้น หากอินพุตเป็น s ="++++" ผลลัพธ์จะเป็นจริง เนื่องจากผู้เล่นเริ่มต้นสามารถรับประกันชัยชนะได้โดยการพลิก "++" ตรงกลางให้เป็น "+--+"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดบันทึกแผนที่หนึ่งรายการ
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้เวลา s
-
ถ้าอยู่ในบันทึกแล้ว −
-
บันทึกการส่งคืน[s]
-
-
เป็นไปได้ :=เท็จ
-
n :=ขนาดของ s
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ถ้า s[i] เหมือนกับ '+' และ s[i + 1] เหมือนกับ '+' ดังนั้น −
-
s[i] :='-', s[i + 1] :='-'
-
เป็นไปได้ :=เป็นไปได้หรือผกผันของการแก้ปัญหา
-
s[i] :='+', s[i + 1] :='+'
-
ถ้าเป็นไปได้ไม่ใช่ศูนย์ ดังนั้น −
-
บันทึกช่วยจำ [s] :=เป็นไปได้
-
-
-
-
บันทึกช่วยจำ [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
