Google 2016 面试题7 翻转游戏（Flip Game II）

你和你的朋友正在玩一个翻转游戏：给定一个只包含'+'和'-'的字符串，你和你的朋友轮流进行以下操作：翻转两个连续的'+'，使得”++”变成”—”。无法进行操作的一方为输。那么给出一个字符串，假设你先进行操作，你是否一定会赢呢？...

(点击上方关注九章算法，获取最新IT求职干货！)

1题目描述

你和你的朋友正在玩一个翻转游戏：给定一个只包含'+'和'-'的字符串，你和你的朋友轮流进行以下操作：翻转两个连续的'+'，使得”++”变成”—”。无法进行操作的一方为输。那么给出一个字符串，假设你先进行操作，你是否一定会赢呢？Example：

s = "-++++-"

返回true，表示你一定会赢。只需翻转第二个和第三个加号使得

s = "-+--+-"

此时对方无法继续操作（没有两个连续的加号）。

2分析解答 1

本题中每个人每次可以进行的操作是有限的，而且经过若干步后一定有一方无法操作，因此可以用枚举＋搜索的方法解决。从直觉上讲，一个状态有三种可能，先进行操作的一方必胜、必败或者不确定结果。那么不确定的结果合理吗？如果一个状态是不确定的结果，那么其可能推出的子状态中不可能存在必败状态（否则该状态就是必胜）；也不可能子状态全为必胜（否则该状态就是必败）；也就是说，子状态中必有一个也是不确定结果。如此直到无法继续操作，显然不存在不确定结果（必有一方胜或者败）。经过推理我们排除了不确定状态的存在，也让搜索的思路更加清晰。从初始状态开始，穷举所有连续加号进行翻转，如果存在某种翻转使得子状态必败，那么该状态必胜；否则该状态必败。

3参考程序  1

4分析解答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

6面试官角度分析

本题普通的搜索也可以通过，在面试中可以勉强达到hire。如果有一些Nim博弈的基础并且给出该题证明可以达到strong hire。

7相关 LintCode 练习题目

http://www.lintcode.com/en/problem/coins-in-a-line-iii/

http://www.lintcode.com/en/problem/coins-in-a-line-ii/

http://www.lintcode.com/en/problem/coins-in-a-line/

点击文末“阅读原文”，即可查看题目。

Google 2016 面试题：点击可阅读

Google 2016 面试题6 | 数组计数

Google 2016 面试题5 | 岛屿计数2

Google 2016 面试题4 | 矩阵中的最长上升路径

Google 2016 面试题3 | 摆动排序 II

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题1 | 数组补丁

关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等；

简介九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。

目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。

目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。

更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.

    关注 九章算法