Google Interview - Flip Game - 我的博客 - ITeye技术网站
http://www.1point3acres.com/bbs/thread-137953-1-1.html
这种解法需要了解博弈论的知识，一般面试应该是不做要求的。只是放在这里供大家参考：
首先，这种游戏属于“无偏博弈”(impartial game)，意思是：“棋盘”上的棋子，即"+"号，双方都可以公平地使用；而且胜利的最终判定方法对二者来说是一样的。而象棋就不是无偏博弈，因为双方各有不同的棋子和胜利条件。其次这种游戏的终结条件是“正常终结条件”的，即最后无法move的那个人输。与之相对的还有一种叫做“misere终结条件”，即无法move的人赢。
以下将要谈到的所有定理和推理过程，都是仅适用于“无偏博弈”和“正常终结条件”的情况。
------------------------------
因为我们只能把连着的两个+号变为-号，所以对我们来说，“棋盘”状态可以由一组“连续的+的个数来表示”，比如“+++----+-++----++++”可以表示为(3, 1, 2, 4)。 因为其中那个单独的+号对结果没有影响，而且3和2出现的顺序也无关紧要，所以我们扔掉“1”，然后将这个序列排序，即得较简的表达方式：(2,3,4)。
所以，这个游戏其实就是从某个初始状态开始，不断进入下一个状态，直至无法改变状态为止。如果以每一个可能的状态做为一个节点，那么整个游戏中能出现的所有状态和这些状态直接的转移方式共同构成了一个有向无环图。之所以无环，是因为我们没法将-号变回+号，所以我们永远不可能回到之前的状态。
比如，从状态(2, 3, 4)开始，我们能进入的可能状态是
(2-2, 3, 4) => (3,4)
(2, 3-1, 4) => (2,4)
(2, 3, 4-2) => (2,2,3)
(2, 3, 2, 2) => (2,2,2,3)
由于游戏结束时序列中必然没有连续的两个+号，所以按照我们的简化记法，此时的状态为().
接下来是两个重要概念，第一是Sprague-Grundy（SG）函数g(x)，其中x是“游戏图”中的一个节点（状态），如果我们用{y1, y2, ..., yn}表示x的所有子节点（即下一步状态）。那么SG函数的定义是：
g(x) = FirstMissingNumber(g(y1), g(y2), ... g(y3))
这是个递归定义的函数。如果x没有子节点，那么定义g(x) = 0；如果x有n个子节点，比如有3个子节点，g值分别为{0,1,3}，那么g(x)的值是这个列表中第一个没有出现的>=0的值，此时g(x) = 2。
为什么需要引入这样一个函数？此处给出一个定理，各位暂时承认他即可：
------------
定理1：如果一个节点x的g(x)=0，那么x状态一定是“先手必输”的状态；否则一定是“先手必赢”。
------------
因此，我们如果能递归算出g(字符串初始状态)的值，那么我们就可以立即判断输赢。
但是，递归计算这个式子会比较繁琐。因为，一个连续序列经常会被分割成两个不连续的序列，这样递归计算的复杂度会比较高。所以我们引入第二个定理，即著名的Sprague-Grundy定理：
------------
定理2：如果一个游戏G由许多相同规则的子游戏G1,G2,..., Gk组成，那么对于游戏G的一个状态x = {x1,x2,...,xn}，SG函数g(x) = g(x1) ^ g(x2) ^ ... ^ g(xn)。其中^表示“异或”。
------------
在我们这个游戏里，多个不相邻的+++子序列，就可以看做多个子游戏。所以，我们就可以用DP来代替递归了，比如当前状态为(10)，它的后继状态可能是(8), (7), (2,6), (3,5), (4,4)。这里，我们就没有必要再次递归去算(2,6), (3,5)和(4,4)，因为根据SG定理, g((2,6)) = g(2) ^ g(6), g((3,5)) = g(3) ^ g(5) ....一般地，对于各种可能状态，我们有如下的计算公式：
另外，如果最初的状态不是一个连续的+号序列，而是几个不连续的+号序列，比如x = (2,3,8)。 那么我们只要分别算x1 = (2), x2 = (3), x3 = (8)三种情况的g值，然后三者取异或即可，对时间空间复杂度没有影响。
Read full article from Google Interview - Flip Game - 我的博客 - ITeye技术网站
算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的＋＋将他们变成－－，如果某个玩家发现对方无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
Followup 如何优化，时间上和空间上。
http://shibaili.blogspot.com/2015/07/google-interview-questions-4.html
第一问：generate all possible moves
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O
补充内容 (2015-7-12 13:13):
下个人没法flip了这个人就赢；all possible moves for next flip
permutation, O(n!)
T(n) = T(n - 1) + T(n - 1) + T(n - 1)...... + c = (n - 1) * T(n - 1) + c
T(n - 1) = (n - 2) * T(n - 2)
T(n - 2) = (n - 3) * T(n - 2)
.....
So T(n) = n!
X. Brute Forcehttp://shibaili.blogspot.com/2015/07/google-interview-questions-4.html
第一问：generate all possible moves
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O
补充内容 (2015-7-12 13:13):
下个人没法flip了这个人就赢；all possible moves for next flip
permutation, O(n!)
T(n) = T(n - 1) + T(n - 1) + T(n - 1)...... + c = (n - 1) * T(n - 1) + c
T(n - 1) = (n - 2) * T(n - 2)
T(n - 2) = (n - 3) * T(n - 2)
.....
So T(n) = n!
- public boolean canWin(char[] s) {
- int start = -1;
- for (int i = 0; i < s.length; i++) {
- if (s[i] == '+') {
- if (start != -1 && i - start > 0) {
- char[] t = Arrays.copyOf(s, s.length);
- t[start] = t[i] = '-';
- if (!canWin(t)) return true;
- start++;
- }else {
- start = i;
- }
- }else {
- start = -1;
- }
- }
- return false;
- }
http://www.1point3acres.com/bbs/thread-137953-1-1.html
这种解法需要了解博弈论的知识，一般面试应该是不做要求的。只是放在这里供大家参考：
首先，这种游戏属于“无偏博弈”(impartial game)，意思是：“棋盘”上的棋子，即"+"号，双方都可以公平地使用；而且胜利的最终判定方法对二者来说是一样的。而象棋就不是无偏博弈，因为双方各有不同的棋子和胜利条件。其次这种游戏的终结条件是“正常终结条件”的，即最后无法move的那个人输。与之相对的还有一种叫做“misere终结条件”，即无法move的人赢。
以下将要谈到的所有定理和推理过程，都是仅适用于“无偏博弈”和“正常终结条件”的情况。
------------------------------
因为我们只能把连着的两个+号变为-号，所以对我们来说，“棋盘”状态可以由一组“连续的+的个数来表示”，比如“+++----+-++----++++”可以表示为(3, 1, 2, 4)。 因为其中那个单独的+号对结果没有影响，而且3和2出现的顺序也无关紧要，所以我们扔掉“1”，然后将这个序列排序，即得较简的表达方式：(2,3,4)。
所以，这个游戏其实就是从某个初始状态开始，不断进入下一个状态，直至无法改变状态为止。如果以每一个可能的状态做为一个节点，那么整个游戏中能出现的所有状态和这些状态直接的转移方式共同构成了一个有向无环图。之所以无环，是因为我们没法将-号变回+号，所以我们永远不可能回到之前的状态。
比如，从状态(2, 3, 4)开始，我们能进入的可能状态是
(2-2, 3, 4) => (3,4)
(2, 3-1, 4) => (2,4)
(2, 3, 4-2) => (2,2,3)
(2, 3, 2, 2) => (2,2,2,3)
由于游戏结束时序列中必然没有连续的两个+号，所以按照我们的简化记法，此时的状态为().
接下来是两个重要概念，第一是Sprague-Grundy（SG）函数g(x)，其中x是“游戏图”中的一个节点（状态），如果我们用{y1, y2, ..., yn}表示x的所有子节点（即下一步状态）。那么SG函数的定义是：
g(x) = FirstMissingNumber(g(y1), g(y2), ... g(y3))
这是个递归定义的函数。如果x没有子节点，那么定义g(x) = 0；如果x有n个子节点，比如有3个子节点，g值分别为{0,1,3}，那么g(x)的值是这个列表中第一个没有出现的>=0的值，此时g(x) = 2。
为什么需要引入这样一个函数？此处给出一个定理，各位暂时承认他即可：
------------
定理1：如果一个节点x的g(x)=0，那么x状态一定是“先手必输”的状态；否则一定是“先手必赢”。
------------
因此，我们如果能递归算出g(字符串初始状态)的值，那么我们就可以立即判断输赢。
但是，递归计算这个式子会比较繁琐。因为，一个连续序列经常会被分割成两个不连续的序列，这样递归计算的复杂度会比较高。所以我们引入第二个定理，即著名的Sprague-Grundy定理：
------------
定理2：如果一个游戏G由许多相同规则的子游戏G1,G2,..., Gk组成，那么对于游戏G的一个状态x = {x1,x2,...,xn}，SG函数g(x) = g(x1) ^ g(x2) ^ ... ^ g(xn)。其中^表示“异或”。
------------
在我们这个游戏里，多个不相邻的+++子序列，就可以看做多个子游戏。所以，我们就可以用DP来代替递归了，比如当前状态为(10)，它的后继状态可能是(8), (7), (2,6), (3,5), (4,4)。这里，我们就没有必要再次递归去算(2,6), (3,5)和(4,4)，因为根据SG定理, g((2,6)) = g(2) ^ g(6), g((3,5)) = g(3) ^ g(5) ....一般地，对于各种可能状态，我们有如下的计算公式：
g(0) = 0; // 一个+都没有，先手必输
g(1) = 0; // 只有一个+，先手必输
g(2) = FirstMissingNumber(g(0)) = 1 // 两个+，先手必赢
g(3) = FirstMissingNumber(g(1)) = 1 // 先手必赢
g(4) = FMN(g(2), g(1) XOR g(1)) = 2 // 两种情况：A 1111->0011 OR 1100，也就是状态2，B 1111-> 1001
...
g(9) = FMN(g(0)^g(7), g(1)^g(6), g(2)^g(5), g(3)^(4)).
...
g(x) = FMN(g(0)^g(x-2), g(1)^g(x-3), g(2)^g(x-4), ... g(x/2)^g(x/2)).
因为计算每一个g(x)都要进行x/2次异或，且FirstMissingNumber也是一个O(x)的操作，所以计算g(1)~g(x)共需要O(x^2)时间。在长为N的“棋盘”上，最大的连续+串的长也为N，所以最差时间复杂度是O(N^2)。需要额外空间保存[0, 1,2,3,4,5...N]状态下的g值，因此空间复杂度是O(N)。
另外，如果最初的状态不是一个连续的+号序列，而是几个不连续的+号序列，比如x = (2,3,8)。 那么我们只要分别算x1 = (2), x2 = (3), x3 = (8)三种情况的g值，然后三者取异或即可，对时间空间复杂度没有影响。
Read full article from Google Interview - Flip Game - 我的博客 - ITeye技术网站
