292. Nim游戏(Python)

作者: 玖月晴 | 来源:发表于2019-05-16 09:12 被阅读0次

题目

难度:★★☆☆☆
类型:数学

你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。

示例

输入: 4
输出: false
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

解答

这是道有趣的智力题。我们首先考虑什么情况下能赢,从示例可以看到,当只剩下4块石头时,轮到谁拿谁输,因为另一个人总是可以把剩下的石头全部拿完。

那么胜利目标就成为希望自己拿走石头后保证还剩4块石头,怎样才能做到呢?同样的道理,只需要还剩8块石头的时候轮到了对方拿,那么不管对方拿多少,1个2个或者3个,自己拿的时候都可以保证只剩4块石头,那怎么保证还剩8块石头的时候轮到了对方拿呢……

综上,我们可以得出,只要我们能够保证自己这轮拿走石头后,剩余的石头个数是4的整数倍,这时轮到谁拿谁输,就可以逼死队友,这样问题就很简单,如果给定的石头个数不是4的整数倍,那么这种情况就稳胜,否则就会输(如果队友掌握了以上技巧的话)。

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

如有疑问或建议,欢迎评论区留言~

相关文章

  • Leetcode PHP题解--D64 292. Nim Gam

    D64 292. Nim Game 题目链接 292. Nim Game 题目分析 假设你和朋友玩一个捡石头的游戏...

  • 292. Nim游戏(Python)

    题目 难度:★★☆☆☆类型:数学 你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1...

  • Leetcode-292Nim Game

    292. Nim Game You are playing the following Nim Game with...

  • 292. Nim游戏

    你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头...

  • 292. Nim 游戏

    你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石...

  • 292. Nim 游戏

    你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石...

  • 2019-02-09

    LeetCode 292. Nim Game Description You are playing the fo...

  • LeetCode 292. Nim游戏

    题目描述: 你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉...

  • 寒假作业

    数字 9. 回文数 7. 整数反转 172. 阶乘后的零 292. Nim 游戏 字符串 字符判断 520. 检测...

  • [LeetCode By Python] 292. Nim Ga

    一、题目 二、解题 互相拿球谁先拿完问题:1)0~3个球:直接拿对应的数字就赢。2)4个球:无论先拿的拿1、2、3...

网友评论

    本文标题:292. Nim游戏(Python)

    本文链接:https://www.haomeiwen.com/subject/ioapaqtx.html