作者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/m.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