294. Flip Game II

 

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.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.

 

这道题是之前那道 Flip Game 的拓展,让我们判断先手的玩家是否能赢,可以穷举所有的情况,用回溯法来解题,思路跟上面那题类似,也是从第二个字母开始遍历整个字符串,如果当前字母和之前那个字母都是+,那么递归调用将这两个位置变为–的字符串,如果返回 false,说明当前玩家可以赢,结束循环返回 false。这里同时贴上热心网友 iffalse 的解释,这道题不是问 “1p是否会怎么选都会赢”,而是 “如果1p每次都选特别的两个+,最终他会不会赢”。所以 canWin 这个函数的意思是 “在当前这种状态下,至少有一种选法,能够让他赢”。而 (!canWin) 的意思就变成了 “在当前这种状态下,无论怎么选,都不能赢”。所以 1p 要看的是,是否存在这样一种情况,无论 2p 怎么选,都不会赢。所以只要有一个 (!canWin),1p 就可以确定他会赢。这道题从博弈论的角度会更好理解。每个 player 都想让自己赢,所以每轮他们不会随机选+。每一轮的 player 会选能够让对手输的+。如果无论如何都选不到让对手输的+,那么只能是当前的 player 输了,参见代码如下:

 

解法一:

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;
    }
};

 

第二种解法和第一种解法一样,只是用 find 函数来查找 ++ 的位置,然后把位置赋值给i,然后还是递归调用 canWin 函数,参见代码如下:

 

解法二:

class Solution {
public:
    bool canWin(string s) {
        for (int i = -1; (i = s.find("++", i + 1)) >= 0;) {
            if (!canWin(s.substr(0, i) + "--" + s.substr(i + 2))) {
                return true;
            }
        }
        return false;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/294

 

类似题目:

Nim Game 

Flip Game

Guess Number Higher or Lower II

Can I Win

 

参考资料:

https://leetcode.com/problems/flip-game-ii/

https://leetcode.com/problems/flip-game-ii/discuss/74033/4-line-Java-Solution

https://leetcode.com/problems/flip-game-ii/discuss/74010/Short-Java-and-Ruby

https://leetcode.com/problems/flip-game-ii/discuss/73962/Share-my-Java-backtracking-solution

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation