LeetCode 292. Nim Game (取物游戏)
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
题目标签:Brainteaser
这道题目给我们一个数字,代表是石头的数量,让我们判断,能赢还是没机会赢,这里假设两个玩家都是有最精确的策略。还有就是,游戏里我是先走的那个,而且每个人一次只能取1或者2或者3个石头。
那我们来举例子看一下:
n 我
1 win
2 win
3 win
4 lose
5 win
6 win
7 win
8 lose
9 win
10 win
11 win
12 lose
我们看到,只有在4的倍数的情况下,我们会输。来分析一下,当给的数字是4的倍数时候,无论我们怎么拿,拿1,2,3。对方都能够化解,然后返回给我们一个4的倍数,这里的策略就是,谁能给对方留下一个4的倍数,就一定能赢。换一句话说,就是谁拿到4的倍数一定会输(除非对方失误)。在不是拿到4的倍数的情况下,只要每一次留给对方4的倍数,我们就可以一直保持到倒数第三轮,给对方4, 对方无论拿走1,2,3, 我们都能一次拿完。
Java Solution:
Runtime beats 6.87%
完成日期:07/10/2017
关键词:Brainteaser
关键点:因为我们只能拿1,2,3块石头,所以4这个数字就是关键
public class Solution
{
public boolean canWinNim(int n)
{
if(n % 4 == 0)
return false;
else
return true;
}
}
参考资料:
http://www.cnblogs.com/grandyang/p/4873248.html
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
最新文章
- CentOS集群安装Tmux
- [问题2014A07] 复旦高等代数 I(14级)每周一题(第九教学周)
- 【转】STM32定时器输出比较模式中的疑惑
- 轻松搞定面试中的二叉树题目(java&;python)
- 解决Android SDK Manager 更新、下载慢以及待安装包列表不显示
- windows 8 系统部署IIS并发布网站
- CSS架构
- Expanding Rods(二分POJ1905)
- update openssl on redhat/centos
- 字符串匹配--kmp算法原理整理
- java commons-lang 工具包 逃脱工具 转unicode 及其他
- wap上传图片跨域发送post请求
- HTML5储存
- QTDesigner的QVBoxLayout自动随窗口拉伸
- 在delphi中,DLL加载时做初始化的Demo
- 【学习】条码扫描器:QuaggaJS
- ajax提交数组至后台,无法获取值得问题
- linux 下shell脚本备份文件
- linux C遍历目录下文件
- [转]使用python来操作redis用法详解