292.Nim游戏--leetcode

题目描述:

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

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

示例:

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

算法设计与分析:

  • 如果堆中的石头的数量n不能被4整除,那么你总是可以赢得Nim游戏的胜利。
  • 从最简单的开始,4块石头,无论拿掉1、2、3块石头,最后对手都可以拿走所有,同样的如果是8块,最后不可避免的让对手拿掉随后一块石头,因为你不能控制最后只剩下四块石头给对手。
  • 于是可以得到规律,当n = 4,8,12,16,20,...等数时候,会输掉比赛,所要避免n取4的倍数。
  • 使用Python3描述算法如下:
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0 
上一篇:LeetCode_292. Nim Game


下一篇:Leetcode 292. Nim 游戏