摘要:前言原题目,内容如下你和你的朋友,两个人一起玩游戏桌子上有一堆石头,每次你们轮流拿掉块石头。编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
前言
原题目,内容如下:
你和你的朋友,两个人一起玩 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; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/76686.html
摘要:拿到最后一颗石头的一方为剩方。现给定一个石头数量,判断你最终是否能取得胜利。对方全拿,对方赢。因此,必输无疑。当剩下的石头为的整数倍双方都采取最优策略时,先下手的一方为输家。因此这个题目就很简单了,只要判断给定的数字是否是的整数倍即可。 D64 292. Nim Game 题目链接 292. Nim Game 题目分析 假设你和朋友玩一个捡石头的游戏,你和朋友轮流拿1~3颗石头。拿到最...
摘要:题目链接思路博弈论类型的题目。总结规律得知,的倍数时,先走的必败。算法复杂度时间空间代码 题目链接:Nim Game 思路:博弈论类型的题目。我们知道,如果是1,2,3,则先走的必胜,4,则先走的必败。总结规律得知,4的倍数时,先走的必败。 算法复杂度: 时间:O(n) 空间:O(1) 代码: class Solution(object): def canWinNim(sel...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
阅读 2478·2021-09-02 15:40
阅读 1533·2019-08-30 15:54
阅读 1049·2019-08-30 12:48
阅读 3349·2019-08-29 17:23
阅读 1022·2019-08-28 18:04
阅读 3628·2019-08-26 13:54
阅读 571·2019-08-26 11:40
阅读 2362·2019-08-26 10:15