LeetCode 292. Nim Game.jpg
LeetCode 292. Nim Game
Description
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.
Example:
Input: 4
Output: false
Explanation: 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.
描述
你和你的朋友，兩個(gè)人一起玩 Nim游戲：桌子上有一堆石頭魂爪，每次你們輪流拿掉 1 - 3 塊石頭先舷。 拿掉最后一塊石頭的人就是獲勝者。你作為先手滓侍。
你們是聰明人蒋川，每一步都是最優(yōu)解。 編寫一個(gè)函數(shù)撩笆，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲捺球。
示例:
輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭缸浦，那么你永遠(yuǎn)不會(huì)贏得比賽；
因?yàn)闊o論你拿走 1 塊氮兵、2 塊 還是 3 塊石頭裂逐，最后一塊石頭總是會(huì)被你的朋友拿走。
思路
- 我先拿
- 如果有1到3塊是否泣栈，先拿的一定贏
- 如果有4塊先拿的一定輸卜高；
- 如果有5個(gè)，我先拿1個(gè)南片，剩下四個(gè)掺涛，此時(shí)對(duì)手的情況和在有4快我先拿的情況一樣，由于有4個(gè)先拿的一定輸疼进，所以對(duì)手一定輸薪缆，所以我一定贏
- 如果有6個(gè)，我先拿2個(gè)伞广，此時(shí)剩下4個(gè)拣帽，在有4快的情況下先拿的一定輸，所以對(duì)手一定輸嚼锄，所以我一定贏
- 如果有7個(gè)减拭，我先拿3個(gè)，此時(shí)剩下4個(gè)灾票，在有4快的情況下先拿的一定輸峡谊，所以對(duì)手一定輸，所以我一定贏
- 如果有8個(gè)刊苍，我先拿3個(gè)，此時(shí)剩下5個(gè)濒析，有5塊先拿的一定贏正什，我一定輸；如果我先拿2快号杏，此時(shí)剩6塊婴氮，有6塊先拿的一定贏，我一定輸盾致；如果我先拿1快主经，此時(shí)剩7塊，有7塊先拿的一定贏庭惜，我一定輸罩驻；所以有8塊我一定輸
- 如果有9塊，我先拿1塊护赊，此時(shí)剩下8塊惠遏，有8塊先拿的一定輸砾跃，所以我一定贏
- 即每4塊一個(gè)循環(huán)，前三個(gè)贏节吮，最后一個(gè)輸抽高；
- 我們對(duì)給定的數(shù)模上4，如果結(jié)果為0說明是4的倍數(shù)透绩，一定輸翘骂，否則一定贏
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-08 11:59:57
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-08 12:23:10
class Solution:
def canWinNim(self, n: 'int') -> 'bool':
# 如果是4的倍數(shù)，一定會(huì)失敗
if not n % 4: return False
# 否則一定贏帚豪，返回True
return True
源代碼文件在這里.
?本文首發(fā)于何睿的博客雏胃，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來源志鞍，作者信息和本聲明.
