Leetcode PHP题解--D64 292. Nim Game

XGBCCC 发布于2019-07-01 12:48 / 1669人阅读

摘要：拿到最后一颗石头的一方为剩方。现给定一个石头数量，判断你最终是否能取得胜利。对方全拿，对方赢。因此，必输无疑。当剩下的石头为的整数倍双方都采取最优策略时，先下手的一方为输家。因此这个题目就很简单了，只要判断给定的数字是否是的整数倍即可。

D64 292. Nim Game 题目链接

292. Nim Game

题目分析

假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。
同时假设你和你的朋友都足够聪明，每次都能采取最优策略。

现给定一个石头数量，判断你最终是否能取得胜利。

思路

我们先从少一点开始推广到n个石头。

如果有1～3颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下1

假设有4颗石头。
你拿1颗，会剩下3颗。对方全拿，对方赢。
你拿2颗，会剩下2颗。对方全拿，对方赢。
你拿3颗，会剩下1颗。对方全拿，对方赢。
即，怎么拿都是你输。

假设有5颗石头。
你拿1颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
你拿2颗，会剩下3颗。对方全拿，对方赢。
你拿3颗，会剩下2颗。对方全拿，对方赢。
因此，这一轮你会选择拿1颗，剩下4颗。

假设有6颗石头。
你拿1颗，会剩下5颗。
对方拿走1颗，剩下4颗给你，参考一开始就只有4颗的情况，对方赢。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
你拿2颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
你拿3颗，会剩下3颗。对方全拿，对方赢。
因此，这一轮你会选择拿2颗，剩下4颗。

假设有7颗石头。
你拿1颗，会剩下6颗。
对方拿走1颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。
对方拿走2颗，剩下4颗给你，对方赢。
对方拿走3颗，剩下3颗给你，你全拿，你赢。
你拿2颗，会剩下5颗。
对方拿走1颗，剩下4颗给你，对方赢。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
你拿3颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
因此，这一轮你会选择拿3颗，剩下4颗。

假设有8颗石头。
你拿1颗，会剩下7颗。
对方拿走1颗，剩下6颗给你，参考一开始就只有6颗的情况，你赢。
对方拿走2颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。
对方拿走3颗，剩下4颗给你，对方赢。
你拿2颗，会剩下6颗。
对方拿走1颗，剩下5颗给你，你赢。
对方拿走2颗，剩下4颗给你，对方赢。
对方拿走3颗，剩下3颗给你，你全拿，你赢。
你拿3颗，会剩下5颗。
对方拿走1颗，剩下4颗给你，对方赢。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
因此，必输无疑。

我们可以得出规律。当剩下的石头为4的整数倍、双方都采取最优策略时，先下手的一方为输家。

因此这个题目就很简单了，只要判断给定的数字是否是4的整数倍即可。

最终代码

若觉得本文章对你有用，欢迎用爱发电资助。

GPU云服务器云服务器 Nim nk292con 64位php环境题解

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

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

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
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 PHP题解--D37 682. Baseball Game

摘要：题目链接题目分析给定一个字符串数组，每一个字符串有以下形式数字。直接计算得分。。代表上一轮分数无效。思路这题没什么好说的了。用区分各种情况，进行相应处理即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 682. Baseball Game 题目链接 682. Baseball Game 题目分析给定一个字符串数组，每一个字符串有以下形式：数字。直接计算得分。 +。代表本轮...

wzyplus 2019-07-01 12:42 评论0 收藏0
[Leetcode] Nim Game 尼姆游戏

摘要：脑筋急转弯复杂度时间空间思路这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。代码如果一开始就是的倍数，你就输了，因为对方可以用同样的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 评论0 收藏0
前端 | 每天一个 LeetCode

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

张汉庆 2019-08-23 13:42 评论0 收藏0