[Leetcode] Nim Game 尼姆游戏

心已赠人 2022-07-17 04:40 129阅读 0赞

# Nim Game #

> 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.
> 
> For example, 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.

## 脑筋急转弯 ##

### 复杂度 ###

时间 O(1) 空间 O(1)

### 思路 ###

这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。然而编程在这里并没有卵用，策略在于，因为每个人都取不到4个，假设自己后走，要保证每轮自己和对方取得数量的和是4，这样就能确保每轮完后都有4的倍数个石头被取走。这样，如果我们先走的话，先把n除4的余数个石头拿走，这样不管怎样，到最后都会留4个下来，对方取1个你就取3个，对方取2个你就取2个，就必赢了。

### 代码 ###

public class Solution { public boolean canWinNim(int n) { // 如果一开始就是4的倍数，你就输了，因为对方可以用同样的策略 return n % 4 != 0; }

``

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：292. Nim Game Nim 游戏（C语言）

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

朴灿烈づ我的快乐病毒、/ 2023年06月21日 05:58/ 0 赞/ 39 阅读

相关 hdoj3032 Nim or not Nim?（可分解尼姆）

Nim or not Nim? Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768

电玩女神/ 2022年08月26日 00:54/ 0 赞/ 118 阅读

相关 leetcode292——Nim Game

leetcode292——Nim Game 非常有意思的题目。在草稿上画一画，居然歪打正着的过了，后来在discuss那里看见一个大神的精致分析，这里就copy过来分享：

缺乏、安全感/ 2022年08月09日 06:21/ 0 赞/ 131 阅读

相关 leetcode-292.Nim Game

leetcode-292.Nim Game You are playing the following Nim Game with your friend: There

古城微笑少年丶/ 2022年07月27日 16:49/ 0 赞/ 148 阅读

相关 [Leetcode] Nim Game 尼姆游戏

Nim Game > You are playing the following Nim Game with your friend: There is a heap o

心已赠人/ 2022年07月17日 04:40/ 0 赞/ 130 阅读

相关 [leetcode]--292. Nim Game

Question 292 > You are playing the following Nim Game with your friend: There is a heap

今天药忘吃喽~/ 2022年07月11日 14:10/ 0 赞/ 146 阅读

相关 [leetcode]: 292. Nim Game

1.题目描述 You are playing the following Nim Game with your friend: There is a heap of sto

向右看齐/ 2022年06月16日 01:09/ 0 赞/ 166 阅读

相关 leetcode 292. Nim Game Nim游戏

You are playing the following Nim Game with your friend: There is a heap of stones on th

太过爱你忘了你带给我的痛/ 2022年06月08日 14:29/ 0 赞/ 211 阅读

相关 LeetCode 292 Nim Game（Nim游戏）

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

电玩女神/ 2022年05月13日 06:38/ 0 赞/ 238 阅读

相关 [leetcode-292-Nim Game]

You are playing the following Nim Game with your friend: There is a heap of stones on th

逃离我推掉我的手/ 2022年01月06日 11:17/ 0 赞/ 228 阅读