九章演算法 | Google 2016 面試題7：翻轉遊戲（Flip Game II）

01-27

撰文 | JZ

專欄 | 九章演算法

題目描述

你和你的朋友正在玩一個翻轉遊戲：給定一個只包含+和-的字元串，你和你的朋友輪流進行以下操作：翻轉兩個連續的+，使得」++」變成」—」。無法進行操作的一方為輸。那麼給出一個字元串，假設你先進行操作，你是否一定會贏呢？

Example：

s = "-++++-"
返回true，表示你一定會贏。只需翻轉第二個和第三個加號使得
s = "-+--+-"

此時對方無法繼續操作（沒有兩個連續的加號）。

分析解答 1

本題中每個人每次可以進行的操作是有限的，而且經過若干步後一定有一方無法操作，因此可以用枚舉＋搜索的方法解決。

從直覺上講，一個狀態有三種可能，先進行操作的一方必勝、必敗或者不確定結果。那麼不確定的結果合理嗎？如果一個狀態是不確定的結果，那麼其可能推出的子狀態中不可能存在必敗狀態（否則該狀態就是必勝）；也不可能子狀態全為必勝（否則該狀態就是必敗）；也就是說，子狀態中必有一個也是不確定結果。

如此直到無法繼續操作，顯然不存在不確定結果（必有一方勝或者敗）。經過推理我們排除了不確定狀態的存在，也讓搜索的思路更加清晰。從初始狀態開始，窮舉所有連續加號進行翻轉，如果存在某種翻轉使得子狀態必敗，那麼該狀態必勝；否則該狀態必敗。

參考程序 1

分析解答2

此題可以用帶回溯的搜索解決。每次搜索時嘗試翻轉兩個連續加號，如果翻轉後的局面是對手輸，那麼這個翻轉是可行的；否則回溯到原來狀態，繼續搜索下一個可能的翻轉操作。該演算法的時間複雜度是指數級別的，對於小數據尚能handle，對於超長字元串就無能為力了。

於是筆者開始腦洞大開，貪心可行嗎？隨意尋找一組翻轉？不行，如六個連續的+，只有一開始翻轉中間兩個才可以獲勝，似乎沒有一種合適的貪心策略。那麼動態規劃可行嗎？狀態太多(2^n)，難以表示。不過動態規劃的嘗試帶給我們一些思考：對於一個局面，要麼先手必勝，要麼先手必敗。事實上，這個遊戲是一個Nim遊戲。

那麼什麼是Nim遊戲？Nim遊戲滿足以下條件：

1. 兩人博弈

2. 兩人輪流在合法的決策集合中選擇一種操作進行遊戲（本題中是選擇兩個連續加號進行翻轉）

3. 合法的決策集合僅與當前局面有關

4. 當其中一人的合法決策集合為空時，此人負。

Nim遊戲是一種簡單的模型，現實中的象棋、圍棋（Lee Sedol和AlphaGo酣戰中）均不屬於Nim遊戲，因它們的決策集合和哪位選手操作有關（黑棋白棋決策集合不同）。

求解Nim遊戲中某個局面為先手必勝或者先手必敗可以在線性時間內解決；每個局面都有一個Nim值，Nim值等於0為先手必敗，否則先手必勝。在本問題中，局面P可以表示為(a0, a1, a2...an)，其中ai表示第i段連續的加號的長度（減號的作用只是分隔，其數量不影響遊戲結果）。Nim(P) = Nim(a0)^Nim(a1)^...^Nim(an)。證明可見百度百科或Wikipedia（神奇的XOR）。本題中，需要先求出簡單局面的Nim值(Nim(i)表示連續i個加號的局面)，再統計原串的局面異或得到答案。

演算法的整體時間複雜度為O(n^2)，n為原字元串長度。

5參考程序 2

面試官角度分析

本題普通的搜索也可以通過，在面試中可以勉強達到hire。如果有一些Nim博弈的基礎並且給出該題證明可以達到strong hire。