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.
A:
典型的backtrack
每次更改2个位置,然后看剩下的是不是怎么变化也赢不了。
class Solution { public: bool canWin(string s) { return helper(s); } private: bool helper(string &s){ for(int i =0;i+1<s.length();i++){ if(s[i]=='+' && s[i+1]=='+'){ s[i]=s[i+1] = '-'; if(not helper(s)){ s[i]=s[i+1] = '+';//put back Also need put back return true; } s[i]=s[i+1] = '+';//put back } } return false; } };
Mistakes:
上面的 写成 for(int i =0;i<s.length() -1 ;i++) 就会不对, 仔细想想为什么。 对于"" 的输入。
***************method 2*******************
数出 ++ 的个数。 分别计算
如果是2,3.只能一个move。 如果是4, first Player可以选择留给1个还是0个。
No comments:
Post a Comment