[問題] Leetcode 294 Flip Game II

看板 Prob_Solve
作者
時間
留言 0則留言,0人參與討論
推噓 0  ( 0推 0噓 0→ )
(更新)發現是 Leetcode 的 test case 不夠完整造成的誤會,感謝收看。 因為是鎖起來的題目所以直接貼: 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 S --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.245.65.132 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1575793310.A.E66.html wheels:轉錄至看板 Soft_Job 12/08 16:23 ※ 編輯: wheels (60.245.65.132 臺灣), 12/08/2019 19:06:07