[請益] Leetcode 294 Flip Game II
（更新）是 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
→
12/08 16:45,
6年前
, 1F
12/08 16:45, 1F
噓
12/08 16:48,
6年前
, 2F
12/08 16:48, 2F
不用，boolean context 下會自己拿 boolean conversion
還有這方法 time/space 都 100% 屌打 DP
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 17:11:38
推
12/08 17:13,
6年前
, 3F
12/08 17:13, 3F
→
12/08 17:17,
6年前
, 4F
12/08 17:17, 4F
推
12/08 17:22,
6年前
, 5F
12/08 17:22, 5F
我也在猜好像跟 S-G theorem 有關，感謝。
但這看起來好像又跟賽局的做法不太一樣 @@?
尤其是 length % 4 != 1 和 length |= 1 用的很神奇
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 17:40:29
噓
12/08 17:49,
6年前
, 6F
12/08 17:49, 6F
→
12/08 17:50,
6年前
, 7F
12/08 17:50, 7F
其實你也沒錯，有寫 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
推
12/08 18:20,
6年前
, 8F
12/08 18:20, 8F
→
12/08 18:30,
6年前
, 9F
12/08 18:30, 9F
→
12/08 18:31,
6年前
, 10F
12/08 18:31, 10F
→
12/08 18:31,
6年前
, 11F
12/08 18:31, 11F
沒錯，這樣可以過，我目前看起來它好像找到了某些 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
→
12/08 19:01,
6年前
, 12F
12/08 19:01, 12F
→
12/08 19:02,
6年前
, 13F
12/08 19:02, 13F
b 大謝謝你不離不棄陪我 QQ
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 19:03:35
※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 19:04:27
推
12/09 13:49,
6年前
, 14F
12/09 13:49, 14F
推
01/22 13:24,
7年前
, 15F
01/22 13:24, 15F