[Leetcode] Nim Game 尼姆游戏

心已赠人 2022-07-17 04:40 148阅读 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 条评论，148人围观）

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

相关阅读

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

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

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

相关【POJ】2234 - Matches Game（尼姆博弈 / Nim游戏）

> 原题链接：[http://poj.org/problem?id=2234][http_poj.org_problem_id_2234] 思路：尼姆博弈的裸题。

比眉伴天荒/ 2023年05月28日 14:20/ 0 赞/ 11 阅读

相关 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 赞/ 127 阅读

相关 LeetCode-Nim Game

Problem: > > You are playing the following Nim Game with your friend: There is a hea

迷南。/ 2022年08月09日 10:00/ 0 赞/ 8 阅读

相关 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 赞/ 159 阅读

相关 [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 赞/ 149 阅读

相关 [Leetcode]Nim Game

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

你的名字/ 2022年06月10日 05:10/ 0 赞/ 126 阅读

相关 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 赞/ 224 阅读

相关 LeetCode 292 Nim Game（Nim游戏）

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

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

相关 [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 赞/ 242 阅读