292-Nim游戏

aboutU 发布于2019-08-19 10:55 / 2582人阅读

摘要：前言原题目，内容如下你和你的朋友，两个人一起玩游戏桌子上有一堆石头，每次你们轮流拿掉块石头。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

前言

原题目，内容如下：

你和你的朋友，两个人一起玩 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;
    }
}

云服务器 GPU云服务器能玩主机游戏的云游戏 html5游戏手机游戏 cdn如何给游戏客户端游戏加速云游戏

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76686.html

Leetcode PHP题解--D64 292. Nim Game

摘要：拿到最后一颗石头的一方为剩方。现给定一个石头数量，判断你最终是否能取得胜利。对方全拿，对方赢。因此，必输无疑。当剩下的石头为的整数倍双方都采取最优策略时，先下手的一方为输家。因此这个题目就很简单了，只要判断给定的数字是否是的整数倍即可。 D64 292. Nim Game 题目链接 292. Nim Game 题目分析假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最...

XGBCCC 2019-07-01 12:48 评论0 收藏0
292. Nim Game

摘要：题目链接思路博弈论类型的题目。总结规律得知，的倍数时，先走的必败。算法复杂度时间空间代码题目链接：Nim Game 思路：博弈论类型的题目。我们知道，如果是1，2，3，则先走的必胜，4，则先走的必败。总结规律得知，4的倍数时，先走的必败。算法复杂度：时间：O(n) 空间：O(1) 代码： class Solution(object): def canWinNim(sel...

April 2019-07-30 17:02 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0