[LeetCode] 294. Flip Game II 翻转游戏 II
2024-10-13 06:17:24
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm's runtime complexity.
293. Flip Game 的拓展，这次求是否先玩者可以有一种策略一定赢游戏。
解法： backtracking
Java:
public class Solution {
public boolean canWin(String s) {
for ( int i = 0; i < s.length() - 1; i ++ ){
if ( s.charAt ( i ) == '+' && s.charAt( i + 1 ) == '+' ){
StringBuilder sb = new StringBuilder ( s );
sb.setCharAt ( i , '-');
sb.setCharAt ( i + 1 ,'-');
if ( !canWin ( sb.toString() ) )
return true;
}
}
return false;
}
}
Java: backtracking
public boolean canWin(String s) {
if(s==null||s.length()==0){
return false;
}
return canWinHelper(s.toCharArray());
}
public boolean canWinHelper(char[] arr){
for(int i=0; i<arr.length-1;i++){
if(arr[i]=='+'&&arr[i+1]=='+'){
arr[i]='-';
arr[i+1]='-';
boolean win = canWinHelper(arr);
arr[i]='+';
arr[i+1]='+';
//if there is a flip which makes the other player lose, the first play wins
if(!win){
return true;
}
}
}
return false;
}
Java: DP, Time Complexity - O(2n)， Space Complexity - O(2n)
public class Solution {
public boolean canWin(String s) {
char[] arr = s.toCharArray();
for(int i = 1; i < s.length(); i++) {
if(arr[i] == '+' && arr[i - 1] == '+') {
arr[i] = '-';
arr[i - 1] = '-';
String next = String.valueOf(arr);
if(!canWin(next)) {
return true;
}
arr[i] = '+';
arr[i - 1] = '+';
}
}
return false;
}
}
Python:
class Solution(object):
def canWin(self, s):
"""
:type s: str
:rtype: bool
"""
for i in range(len(s) - 1): # 寻找所有的翻转可能
if s[i:i+2] == "++":
current = s[0:i] + "--" + s[i+2:] # 把找到的++变成-- if not self.canWin(current): # 看当前的字串是否存在边界，没有++了
return True # 对手不能赢，那就是当前翻转的赢了
return False # loop中没有返回，不能赢，当前翻转的输了
C++:
class Solution {
public:
bool canWin(string s) {
for (int i = 1; i < s.size(); ++i) {
if (s[i] == '+' && s[i - 1] == '+' && !canWin(s.substr(0, i - 1) + "--" + s.substr(i + 1))) {
return true;
}
}
return false;
}
};
C++:
class Solution {
public:
bool canWin(string s) { //朴素回溯，715MS
int len=s.size();
if(len<=1) return false;
for(int i=0;i<len-1;i++) {
string tmp=s;
if(s[i]=='+'&&s[i+1]=='+') {
tmp[i]='-';tmp[i+1]='-';
bool f=canWin(tmp);
if(!f) return true;
}
}
return false;
}
};
C++:
class Solution {
public:
bool canWin(string s) { //记录中间结果，39MS
int len=s.size();
if(len<=1) return false;
if(Memory_Map.find(s)!=Memory_Map.end()) {
return Memory_Map[s];
}
for(int i=0;i<len-1;i++) {
string tmp=s;
if(s[i]=='+'&&s[i+1]=='+') {
tmp[i]='-';tmp[i+1]='-';
bool f=canWin(tmp);
if(!f) {
Memory_Map[s]=true;
return true;
}
}
}
Memory_Map[s]=false;
return false;
}
private:
unordered_map<string,bool> Memory_Map;
};
类似题目：
[LeetCode] 293. Flip Game 翻转游戏
All LeetCode Questions List 题目汇总
最新文章
- USACO翻译：USACO 2013 JAN三题（1）
- vm安装centos 老是出现 grub.conf 配置问题
- 修改CMD字符编码
- 嵌入式Linux学习笔记（0）基础命令。——Arvin
- TimeVal类——Live555源码阅读(一)基本组件类
- 51nod1346 递归
- Migration workstation vms to openstack kvm
- Linux 最新SO_REUSEPORT特性
- ch2-mysql相关
- 数据加密，android客户端和服务器端可共用
- [基础常识]申请免费SSL证书 - 阿里云云盾证书 - Digicert+Symantec 免费型DV SSL
- php函数 array_column
- nginx多虚拟主机优先级location匹配规则及tryfiles的使用
- eclipse webproject activiti
- rviz1
- Android Edittext聚焦时输入法挡住了EditText输入框的两种解决方案
- ScrollView嵌套ListView只显示一行解决方案
- Linux常用指令大全
- java 将字符串数组变为字典顺序排序后的字符串数组
- (解释文)My SQL中主键为0和主键自排约束的关系