[請益] Leetcode 294 Flip Game II

[wheels ()]

（更新）是 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://www.ptt.cc/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
→ illegalplan: 之前programming版會討論
噓 pig2014: DP拉幹，return不用casting喔
不用，boolean context 下會自己拿 boolean conversion

還有這方法 time/space 都 100% 屌打 DP
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 17:11:38
推 s06yji3: 樓上，加油
→ stkoso: 2F484沒寫過python
推 bigelephants: 本質上是個 nim game，可以找一下這個關鍵字
我也在猜好像跟 S-G theorem 有關，感謝。

但這看起來好像又跟賽局的做法不太一樣 @@?

尤其是 length % 4 != 1 和 length |= 1 用的很神奇
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 17:40:29
噓 pig2014: 操，type hint還有這種洨功能，對不起我錯了
→ pig2014: 不嘴炮，我認真覺得這是DP的縮減版
其實你也沒錯，有寫 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
推 chi972121: pig認錯也是用噓的，幫補血
→ bigelephants: length |= 1 基本上應該跟把所有偶數 +1 意思一樣
→ bigelephants: 我沒辦法傳，但我猜你把 length |= 1 刪掉
→ bigelephants: 並且 S ^= {length} 改成 S ^= {length//2} 會一樣
沒錯，這樣可以過，我目前看起來它好像找到了某些 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
→ bigelephants: 能請你傳一下11個+跟6個+的組合嗎?
→ bigelephants: +++++++++++-++++++
b 大謝謝你不離不棄陪我 QQ
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 19:03:35
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 19:04:27
推 gogogogo3333:  game theory, nim sum
推 moon2519: 推個