新题Flip Game II的最快解法（附代码）

Leetcode今天刚放出了一道新题Flip Game II。之前的帖中我曾介绍过这题的DP解法，现在把代码放在这里供感兴趣的同学参考。这段代码在OJ上测试时间是0ms. 比起至少需要50ms左右的回溯法来要快不少：

1. int firstMissingNumber(unordered_set<int> lut) {
   
2.     int m = lut.size();
   
3.     for (int i = 0; i < m; ++i) {
   
4.         if (lut.count(i) == 0) return i;
   
5.     }
   
6.     return m;
   
7. }
   
8. 
   
9. bool canWin(string s) {
   
10.     int curlen = 0, maxlen = 0;
    
11.     vector<int> board_init_state;
    
12.     for (int i = 0; i < s.size(); ++i) {   
    
13.         if (s[i] == '+') curlen++;              // Find the length of all continuous '+' signs
    
14.         if (i+1 == s.size() || s[i] == '-') {
    
15.             if (curlen >= 2) board_init_state.push_back(curlen);    // only length >= 2 counts
    
16.             maxlen = max(maxlen, curlen);       // Also get the maximum continuous length
    
17.             curlen = 0;
    
18.         }
    
19.     }
    
20.     // For instance ++--+--++++-+ will be represented as (2, 4)
    
21. 
    
22.     vector<int> g(maxlen+1, 0);    // Sprague-Grundy function of 0 ~ maxlen
    
23.     for (int len = 2; len <= maxlen; ++len) {
    
24.         unordered_set<int> gsub;    // the S-G value of all subgame states
    
25.         for (int len_first_game = 0; len_first_game < len/2; ++len_first_game) {
    
26.             int len_second_game = len - len_first_game - 2;
    
27.             // Theorem 2: g[game] = g[subgame1]^g[subgame2]^g[subgame3]...;
    
28.             gsub.insert(g[len_first_game] ^ g[len_second_game]);
    
29.         }
    
30.         g[len] = firstMissingNumber(gsub);
    
31.     }
    
32.    
    
33.     int g_final = 0;
    
34.     for (auto& s: board_init_state) g_final ^= g[s];
    
35.     return g_final != 0;    // Theorem 1: First player must win iff g(current_state) != 0
    
36. }

复制代码

stellari 发表于 2015-12-8 09:23
1. 对，canWin()==true是“先手玩家一定能赢（只要先手玩家先做出正确的move）”，而canWin()==false则表 ...

1.所以这题可以认为：
全集=先手玩家必赢+后手玩家必赢
或者说，总存在一个策略，使得要么先手玩家必赢，要么后手玩家必赢。
因为要保证 canWin()+!canWin()各自代表的集合的union等同于全集。

我开始认为的全集是=先手玩家必赢+后手玩家必赢+找不到一个策略使任何玩家必赢

我这么理解对吗？

2.谢谢！

lz真是大牛啊！！想去的公司应该没有去不了的！！膜拜膜拜！！

大神今天才看到你lc上的帖子，有两个问题（而且都是关于recursive算法的...)
1. 这道题的function的return value是指目前的玩家能不能“保证赢”。你贴出来的recursive算法是看换掉一对"++"后第二个人是否能赢。但是如果用  !canWin()的话 我感觉意思不是第二个人是否能赢，而是第二个人是否 “保证赢”。这样即使 !canWin()==true的话也只能说明第二个玩家无法保证必赢，但是还是允许可赢可输（取决于后来第一人的策略）
2. 我现在只是记得 O(N)= sum(O(i)) i=1, 2, ..., N-1代表的是exponential的复杂度，想了半天找了半天也没弄清楚是怎么推导出来的，求大神提示！

七夜雪 发表于 2015-12-8 08:05
大神今天才看到你lc上的帖子，有两个问题（而且都是关于recursive算法的...)
1. 这道题的function的return ...

1. 对，canWin()==true是“先手玩家一定能赢（只要先手玩家先做出正确的move）”，而canWin()==false则表示“后手玩家一定能赢（无论先手玩家选择什么策略）”。

canWin()==true的充要条件是：先手玩家至少有一种策略，使得后手玩家在这种策略下canWin()==false(意思是后手玩家的再后手玩家，即原来的先手玩家，一定能赢)。

相应地，canWin()失败的充要条件是：无论先手玩家怎么走，后手玩家都能保证canWin()。


因此，只要我们找到一种先手策略，使得后手玩家!canWin()，那么先手玩家就肯定能赢。我贴的那个解法就是基于这个推断的。

2. T(N) = [T(1) + T(2) + ... + T(N-2)] + T(N-1) = T(N-1) + T(N-1) = 2*T(N-1) = 4*T(N-2) = 8*T(N-3) = ... 2^(k)*T(N-k) = 2^(N-1) * T(1). 当T(1)是常数时，便有T(N)~O(2^N)。
还有就是，推导的时候你最好是像上面那样用T或其他字母代表运行时间。O(N)的意思就是“线性时间复杂度”，而不是“以N为参数的一个未知的运行时间表达式”。

七夜雪 发表于 2015-12-8 10:05
1.所以这题可以认为：
全集=先手玩家必赢+后手玩家必赢
或者说，总存在一个策略，使得要么先手玩家必赢 ...

是的，impartial game的状态只有两种，要么先手必赢，要么先手必输，不存在第三种状态。关于证明你可以参看：

https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula

这是Nim游戏的的证明，但是任何impartial game游戏都可以归结到Nim游戏。

stellari 发表于 2015-12-8 14:27
是的，impartial game的状态只有两种，要么先手必赢，要么先手必输，不存在第三种状态。关于证明你可以参 ...

Nice!非常感谢！