292-Nim游戏
文章目录
前言
原题目,内容如下:
你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。
解题思路
初看题目的时候可能会感觉无从下手,但是可以先把石头的总数为1到20的输赢情况(赢为true,输为false)列出来,然后从中找到规律:
| 石头数 | 输赢情况 | 石头数 | 输赢情况 |
|---|---|---|---|
| 1 | true | 11 | true |
| 2 | true | 12 | false |
| 3 | true | 13 | true |
| 4 | false | 14 | true |
| 5 | true | 15 | true |
| 6 | true | 16 | false |
| 7 | true | 17 | true |
| 8 | false | 18 | true |
| 9 | true | 19 | true |
| 10 | true | 20 | false |
通过观察输赢情况表格,可以看出逢4必输,为了更加清晰,对表格进行了整理和补充:
| 石头数 | 输赢情况 | 石头数 | 输赢情况 | 石头数 | 输赢情况 |
|---|---|---|---|---|---|
| 1 | true | 9 | true | 17 | true |
| 2 | true | 10 | true | 18 | true |
| 3 | true | 11 | true | 19 | true |
| 4 | false | 12 | false | 20 | false |
| 5 | true | 13 | true | 21 | true |
| 6 | true | 14 | true | 22 | true |
| 7 | true | 15 | true | 23 | true |
| 8 | false | 16 | false | 24 | false |
从整理的表格可以更加明显看出逢4必输的规律,即当石头数为4的倍数时必输。
实现代码
public class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论