[Leetcode] Nim Game 尼姆游戏

cartoon 发布于2019-08-14 12:45 / 3158人阅读

摘要：脑筋急转弯复杂度时间空间思路这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。代码如果一开始就是的倍数，你就输了，因为对方可以用同样的策略

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.

脑筋急转弯 复杂度

时间 O(1) 空间 O(1)

思路

这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。然而编程在这里并没有卵用，策略在于，因为每个人都取不到4个，假设自己后走，要保证每轮自己和对方取得数量的和是4，这样就能确保每轮完后都有4的倍数个石头被取走。这样，如果我们先走的话，先把n除4的余数个石头拿走，这样不管怎样，到最后都会留4个下来，对方取1个你就取3个，对方取2个你就取2个，就必赢了。

代码

public class Solution {
    public boolean canWinNim(int n) {
        // 如果一开始就是4的倍数，你就输了，因为对方可以用同样的策略
        return n % 4 != 0;
    }
}

GPU云服务器云服务器 Nim 尼姆 LeetCode LeetCode_String

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

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

Leetcode PHP题解--D64 292. Nim Game

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

XGBCCC 2019-07-01 12:48 评论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
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] Jump Game 跳跃游戏

摘要：代码记录下当前区域的上界，以便待会更新下一个区域的上界更新下一个区域的上界更新下一个区域的下界后续如果要求返回最短跳跃路径，如何实现可以使用，并根据一个全局最短步数维护一个全局最短路径，当搜索完所有可能后返回这个全局最短路径。 Jump Game I 最新解法请见：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 评论0 收藏0