leetcode with python:292. Nim Game

题目:

You are playing the following Nim Game with your friend:

Initially, there is a heap of stones on the table.
You and your friend will alternate taking turns, and you go first.
On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

你和朋友在玩一个叫Nim Game的游戏,规则如下:
1.有一叠石头,两人轮流,一个人一次能移开1~3个石头,最后把石头拿完的人胜利
2.你是先手
题目会给定一数n表石头数,若在两人都认真玩游戏的情况下
你能赢这场游戏的话回传True,反之回传False

我还蛮喜欢这题的
很像小时候玩的机智问答

class Solution:    def canWinNim(self, n: int) -> bool:        return n%4

我们知道当石头只有4颗且我们先手时是必输之局
我取1朋友取3,我取2朋友取2,我取3朋友取1不管怎样都输
所以我们要营造轮到朋友时石头剩4颗的情境我们才会赢
而只有在石头不是4的倍数时,我们才能营造出这种情境

1.石头为4的倍数:
我们拿x颗,朋友只要拿4-x颗就能维持石头是4的倍数
直到石头是4颗时我们会是先手,所以必输
2.石头不为4的倍数:
我们只要一开始拿掉n%4的石头就能让朋友掉进1.的循环,所以必赢

所以这题只要判断n是否为4的倍数即可
最后执行时间32ms(faster than 90.66%)

那我们下题见