作者wheels ()
看板Soft_Job
标题[请益] Leetcode 294 Flip Game II
时间Sun Dec 8 16:23:10 2019
（更新）是 Leetcode 的 test case 不完整，已发 contribution 了。
想询问演算法问题，刚才看了一下板规好像没写不能问 @@?
如果看错或有任何问题请告知，我会自删，谢谢。
※ [本文转录自 Prob_Solve 看板 #1TxBAUvc ]
作者: wheels () 看板: Prob_Solve
标题: [问题] Leetcode 294 Flip Game II
时间: Sun Dec 8 16:21:48 2019
因为是锁起来的题目所以直接贴：
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.
这题我有用 recursion + memo 解出来，
但看到一个 finding pattern 的方法可以 AC 且 100%，
不过却无法参透它，想请问有没有人可以帮忙说明下，感激不尽。
# Python3
class Solution:
def canWin(self, s: str) -> bool:
S, length = set(), 0
for c in s + '-':
if c == '-':
if length and length % 4 != 1:
length |= 1
S ^= {length}
length = 0
else:
length += 1
return bool(S)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.245.65.132 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1575793310.A.E66.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: wheels (60.245.65.132 台湾), 12/08/2019 16:23:10
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 16:24:53
1F：→ illegalplan: 之前programming版会讨论 12/08 16:45
2F：嘘 pig2014: DP拉干，return不用casting喔 12/08 16:48
不用，boolean context 下会自己拿 boolean conversion
还有这方法 time/space 都 100% 屌打 DP
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 17:11:38
3F：推 s06yji3: 楼上，加油 12/08 17:13
4F：→ stkoso: 2F484没写过python 12/08 17:17
5F：推 bigelephants: 本质上是个 nim game，可以找一下这个关键字 12/08 17:22
我也在猜好像跟 S-G theorem 有关，感谢。
但这看起来好像又跟赛局的做法不太一样 @@?
尤其是 length % 4 != 1 和 length |= 1 用的很神奇
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 17:40:29
6F：嘘 pig2014: 操，type hint还有这种洨功能，对不起我错了 12/08 17:49
7F：→ pig2014: 不嘴炮，我认真觉得这是DP的缩减版 12/08 17:50
其实你也没错，有写 type hint 的话 type checker 在这种情况应该是会叫的
只是使用上不会有问题，原因就是我说的 boolean context conversion，
但为了避免焦点被转移我改一下。
另外，要说这是 DP 其实也行，因为广义来说有用到曾经运算过的资讯就是 DP，
但重点还是在这个解法我看不出它在思考什麽，
因为如果是走 S-G 应该不会有 length % 4 != 1 和 length |= 1 这种魔法才对
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 17:57:26
8F：推 chi972121: pig认错也是用嘘的，帮补血 12/08 18:20
9F：→ bigelephants: length |= 1 基本上应该跟把所有偶数 +1 意思一样 12/08 18:30
10F：→ bigelephants: 我没办法传，但我猜你把 length |= 1 删掉 12/08 18:31
11F：→ bigelephants: 并且 S ^= {length} 改成 S ^= {length//2} 会一样 12/08 18:31
没错，这样可以过，我目前看起来它好像找到了某些 pattern：
1. 4k + 1 一定是 false
2. 连续的奇偶数可以互相消去
还在研究中...
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 18:52:58
结果我发现这个解法能过只是个美丽的错误：
https://imgur.com/a/soexk6N
已经发 contribute 给 leetcode 了 XD
感谢回应的各位，有时跑得过的解不一定是真的解 lol
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 19:02:39
12F：→ bigelephants: 能请你传一下11个+跟6个+的组合吗? 12/08 19:01
13F：→ bigelephants: +++++++++++-++++++ 12/08 19:02
b 大谢谢你不离不弃陪我 QQ
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 19:03:35
※ 编辑: wheels (60.245.65.132 台湾), 12/08/2019 19:04:27
14F：推 gogogogo3333: game theory, nim sum 12/09 13:49
15F：推 moon2519: 推个 01/22 13:24