Skip to content

292 nim game

292. Nim Game

题目:

https://leetcode.com/problems/nim-game/

难度:

Easy

对于总是优先开始的那方

  • 有一到三块,总是赢
  • 有四块,总是输
  • 有五块,总是赢

所以如果自己想赢,总是要迫使对方拿之后,给自己遗留5块,或者三块以及以下。

  • 如果是六块:

    • 拿一块,对方五块,对方赢
    • 拿两块,对方余下四块,我方赢
    • 拿三块,余三块,对方赢
  • 七块:

    • 拿三块,余四块,迫使对方输,总是赢

本打算用递归来看,因为对方也可以重复使用这个函数,但是会超时,所以就看了一下hint

  • n <= 3 能赢 √
  • n == 4 总输
  • n = 5,6,7 总赢
  • n == 8, 先手如何选,总可以转成5,6,7 对方总会赢

所以 n % 4 == 0 时候,先手必输

简直是啊,有些游戏就是这样来必赢的啊,没想到你是这样的题目

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


回到顶部