美国卖车经历分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 9279|回复: 6
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
stellari 发表于 2015-10-16 17:03:43 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】

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

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

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. }
复制代码

评分

参与人数 4大米 +113 收起 理由
阿童木 + 100
xiangmo + 5 回答的很好!
laiguojiuhao + 3 感谢分享!
wcongying + 5 感谢分享!

查看全部评分


上一篇:Letter Combinations of a Phone Number按键组合-细节问题
下一篇:碰到了一道optimal partition的题想请教大家
我的人缘0
七夜雪 发表于 2015-12-8 10:05:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-12-8 09:23
1. 对,canWin()==true是“先手玩家一定能赢(只要先手玩家先做出正确的move)”,而canWin()==false则表 ...

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

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

我这么理解对吗?

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

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
nuanuan1208 发表于 2015-10-17 00:33:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lz真是大牛啊!!想去的公司应该没有去不了的!!膜拜膜拜!!
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| stellari 发表于 2015-12-8 09:23:48 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
七夜雪 发表于 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为参数的一个未知的运行时间表达式”。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| stellari 发表于 2015-12-8 14:27:57 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
七夜雪 发表于 2015-12-8 10:05
1.所以这题可以认为:
全集=先手玩家必赢+后手玩家必赢
或者说,总存在一个策略,使得要么先手玩家必赢 ...

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

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

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

使用道具 举报

我的人缘0
七夜雪 发表于 2015-12-9 05:05:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-12-8 14:27
是的,impartial game的状态只有两种,要么先手必赢,要么先手必输,不存在第三种状态。关于证明你可以参 ...

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-21 16:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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