一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5124|回复: 6
收起左侧

[Leetcode] 新题Flip Game II的最快解法(附代码)

[复制链接] |试试Instant~ |关注本帖
stellari 发表于 2015-10-16 17:03:43 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 stellari 于 2015-10-16 17:03 编辑

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. bool canWin(string s) {
  9.     int curlen = 0, maxlen = 0;
  10.     vector<int> board_init_state;
  11.     for (int i = 0; i < s.size(); ++i) {   
  12.         if (s[i] == '+') curlen++;              // Find the length of all continuous '+' signs
  13.         if (i+1 == s.size() || s[i] == '-') {
  14.             if (curlen >= 2) board_init_state.push_back(curlen);    // only length >= 2 counts
  15.             maxlen = max(maxlen, curlen);       // Also get the maximum continuous length
  16.             curlen = 0;
  17.         }
  18.     }
  19.     // For instance ++--+--++++-+ will be represented as (2, 4)

  20.     vector<int> g(maxlen+1, 0);    // Sprague-Grundy function of 0 ~ maxlen
  21.     for (int len = 2; len <= maxlen; ++len) {
  22.         unordered_set<int> gsub;    // the S-G value of all subgame states
  23.         for (int len_first_game = 0; len_first_game < len/2; ++len_first_game) {
  24.             int len_second_game = len - len_first_game - 2;
  25.             // Theorem 2: g[game] = g[subgame1]^g[subgame2]^g[subgame3]...;
  26.             gsub.insert(g[len_first_game] ^ g[len_second_game]);
  27.         }
  28.         g[len] = firstMissingNumber(gsub);
  29.     }
  30.    
  31.     int g_final = 0;
  32.     for (auto& s: board_init_state) g_final ^= g[s];
  33.     return g_final != 0;    // Theorem 1: First player must win iff g(current_state) != 0
  34. }
复制代码

评分

3

查看全部评分

七夜雪 发表于 2015-12-8 10:05:02 | 显示全部楼层
stellari 发表于 2015-12-8 09:23
1. 对,canWin()==true是“先手玩家一定能赢(只要先手玩家先做出正确的move)”,而canWin()==false则表 ...

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

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

我这么理解对吗?

2.谢谢!
回复 支持 1 反对 0

使用道具 举报

nuanuan1208 发表于 2015-10-17 00:33:42 | 显示全部楼层
lz真是大牛啊!!想去的公司应该没有去不了的!!膜拜膜拜!!
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| stellari 发表于 2015-12-8 09:23:48 | 显示全部楼层
七夜雪 发表于 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为参数的一个未知的运行时间表达式”。
回复 支持 反对

使用道具 举报

 楼主| stellari 发表于 2015-12-8 14:27:57 | 显示全部楼层
七夜雪 发表于 2015-12-8 10:05
1.所以这题可以认为:
全集=先手玩家必赢+后手玩家必赢
或者说,总存在一个策略,使得要么先手玩家必赢 ...

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

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

这是Nim游戏的的证明,但是任何impartial game游戏都可以归结到Nim游戏。
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-9 05:05:15 | 显示全部楼层
stellari 发表于 2015-12-8 14:27
是的,impartial game的状态只有两种,要么先手必赢,要么先手必输,不存在第三种状态。关于证明你可以参 ...

Nice!非常感谢!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 22:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表