这是一个创建于 3637 天前的主题，其中的信息可能已经有所发展或是发生改变。
我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站
牛客网 http://www.nowcoder.com?from=v2ex
里面积累了谷歌、腾讯、百度等几十家互联网公司的笔试面试题目。但网站当前有部分题目还没有楼主觉得认可的最佳答案和解释，为了更好的服务程序猿们，我们做了一个活动，悬赏大牛解答，每道题目根据难度对应一定的现金奖励，最高一道题目奖励100元，还有iPhone6、移动硬盘、小米手环等众多好礼相送。
从今天开始到1月29日，我们会在论坛持续更新本贴，每天放出1-3道题目，欢迎大家跟帖解答，最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天公布。
今日题目
有一堆石子共100枚，甲乙轮流从该堆中取石子，每次可以取2、4或6格，取得最后的石子的玩家为赢家，若甲先取，则(),理由是为什么？
A.甲必胜
B.乙必胜
C.谁都无法必胜
D.不确定牛客网会对用户提交的回答进行敏感词过滤，请设计算法编码实现敏感词过滤的功能。
（欢迎大家一起讨论，明天我们会把牛客网的敏感词过滤功能代码开放出来）
更多有奖答题： http://www.nowcoder.com/activity/challenge?from=v2ex
欢迎大家关注我们，活动结束后我们会把面试题整理成PDF分发给参与的用户
微博 http://www.weibo.com/nowcoder
微信 www_nowcoder_com
技术QQ群 157594705
邮件 [email protected]
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~
昨日答题话费由 @exch4nge @ruoyu0088 @xylophone21 @wgwang 斩获。恭喜！
附昨日帖子地址 http://www.v2ex.com/t/159579
 |
1
happywowwow 2015-01-07 10:29:12 +08:00
2、ac多模匹配算法？ 设置关键词，建立字典表，跳转表，失败表，对输入的字串做一次遍历。得出存在哪些敏感词
|
 |
2
xcv58 2015-01-07 10:30:07 +08:00
每次可以取2、4或6格 -> 个
|
 |
3
lijinma 2015-01-07 10:32:08 +08:00  1
1. 因为每次只能取2,4,6格，所以如果给对手剩下的是8格，你一定会赢。
所以只要剩下的是8的倍数就可以，100 mod 8 为4， 所以你先取4个，之后根据对手取的个数，保持剩下的格子为8的倍数即可。 |
|
4
lijinma 2015-01-07 10:32:33 +08:00
所以甲必胜
|
|
5
happywowwow 2015-01-07 10:32:54 +08:00
理由是为什么？
看着好别扭。。。。。。 |
 |
6
nowcoder OP @happywowwow 求详细设计和相关代码哈
|
 |
7
wgwang 2015-01-07 10:37:54 +08:00
1. 甲必胜
甲先去 4个 ， 剩下96个，刚好被8 整除 然后 不管 乙 取x = any(2, 4, 6) 甲去 y = 8-x 这样每轮取掉8个 最后一个必然被甲取走 |
 |
8
kslr 2015-01-07 10:39:52 +08:00
|
|
9
happywowwow 2015-01-07 10:42:19 +08:00
@nowcoder https://github.com/pikeszfish/ac_engine/blob/master/ac.c 以前写过一个实验这个算法的 代码渣 不太会写c
|
|
10
wgwang 2015-01-07 10:45:55 +08:00
2. 敏感词过滤这个，属于nlp的领域，做得好的话，需要进行语义理解，否则会导致各种神奇的现象。
简单粗暴的话， 单字是效率最高效果最差的；n-gram效果稍微好点，特别是对输入输入文本不大，敏感词表也不大的那种。 机器学习方法的话，可以使用learn to rank类似的方法，据说在退出中国之前google有一套系统是自动学习baidu 的过滤策略的。 |
 |
11
lincanbin 2015-01-07 11:35:50 +08:00 via Android 4
出售一台独立服务器，八口交换机。
你们的敏感词过滤能做到过滤这两个关键词而不过滤上面这句话？ |
 |
13
funky 2015-01-07 11:42:19 +08:00
第一题我觉得LS的各位都是建立在假定甲必胜前提下.但是如果你假定乙必胜,又是另外一番策略,哈哈.
|
 |
14
tabris17 2015-01-07 11:43:18 +08:00
敏感词过滤要做中文分词吗？如果要的话可大可小啊；如果就是匹配过滤的话也没啥可考啊
|
 |
15
mcone 2015-01-07 12:15:39 +08:00
|
|
16
mcone 2015-01-07 12:17:08 +08:00
|
 |
17
lecher 2015-01-07 12:28:33 +08:00
@funky 第一题这个简化版的是有通用模式的，要保证后取的必胜。
那么就是要保证倒数第二次对手取不完的同时，你能把剩下的取完，所以算得倒数第二次要处理的石子是每次可取的最大值和最小值之和。按这题就是2+6。这是每次要处理的单元数据 剩下的就是逆推，你每次都给对手剩下这个单元数据的倍数，就可以按照这个策略取胜。 然后算总数，100除以8 得到12余4，就是说只要先手的人取4个，导致对手只能处理8的倍数。对手必败，如果总数除以要处理单元数据没有余数，就是自己要处理的剩余柿子数恰好是单元数据的倍数，那么就是自己必败。 其实题目已经简化了，如果能取的石子数都是素数，比如2、3、5、7。情况就要复杂一些了。 |
 |
18
theJian 2015-01-07 13:23:06 +08:00
我是用NIM博弈想第一题的(其实说到底跟楼上几位没多少区别，但是我还是很想BB一下),先不考虑总棋子数，假设一个前提，就是第一个人肯定可以取，也就是棋子数不能是[0,1]，那对于玩家来说，面对棋子数是[0,1]的情形就意味输了，这个是N(必败局),容易得到[2,7]是P(必胜局),N与P是可以相互转换的，根据下一个N [8,9]可以看出规律，N与P的循环是这样的{[0,1] [2,7] [8,9] [11,15]..........}，可以得出N的通项[k*8, K*8 + 1],其余的是P,可以算出100是处于P的。
|
 |
19
imn1 2015-01-07 13:23:40 +08:00
每论必能实现的最大值C（一个最大值A + 一个最小值B），求余数D
B<=D<=A，先手胜 其他，后手胜，余数不在先手控制范围内，必定为后手控制 这是程序思路 @funky 这是省略条件的问题，或者说答题者特定理解的问题，省略的条件是：甲乙双方都有足够的推理能力的前提 如果没有这个前提，这题没有意义，不用问了，所以不是假定（逆向推理） |
 |
20
ultimate010 2015-01-07 13:29:59 +08:00
当然ac自动机,网上有非常多的实现.
|
 |
21
aheadlead 2015-01-07 15:58:25 +08:00
ac自动机...第二题
|
 |
22
LukeXuan 2015-01-07 16:38:08 +08:00 via Android
1. NP理论退化版本…第一次取4个 剩下保证剩下8的倍数…其实和50石子 取123效果一样…
2. 朴素的AC就好了…不过效果好要分词 或者 在贝叶斯上做machine learning 吧 |
|
26
nowcoder OP @lijinma 感谢精彩解答，请发手机号码到 [email protected] 我们给你充值。
|
Select Language