292. Nim 游戏

🟢 🔖 脑筋急转弯 数学 博弈 🔗 力扣open in new window LeetCodeopen in new window

题目

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 returnfalse.

Example 1:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

Input: n = 1
Output: true

Example 3:

Input: n = 2
Output: true

Constraints:

1 <= n <= 2^31 - 1

题目大意

你和你的朋友，两个人一起玩 Nim 游戏open in new window：

桌子上有一堆石头。
你们轮流进行自己的回合， **你作为先手 **。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入： n = 4
输出： false
解释： 以下是可能的结果:
移除 1 颗石头。你的朋友移走了 3 块石头，包括最后一块。你的朋友赢了。
移除 2 个石子。你的朋友移走 2 块石头，包括最后一块。你的朋友赢了。
3.你移走 3 颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入： n = 1
输出： true

示例 3：

输入： n = 2
输出： true

提示：

1 <= n <= 2^31 - 1

解题思路

这是一道经典的博弈论问题。解决这类问题的关键在于分析规律和确定必胜/必败局面。

1. 基础分析

如果石头数量 n <= 3，你可以一次性拿完，直接赢得比赛。
如果石头数量 n == 4，无论你拿走 1、2 或 3 块，都会让对手面对剩下的 3、2 或 1 块石头，最终对手会赢。这是一个必败局面。

2. 归纳规律

对于任意数量的石头：

如果 n % 4 == 0，你处于必败局面。
- 原因：不管你拿 1、2 或 3 块石头，都会让对手拿完剩余的石头，从而确保对手获胜。
如果 n % 4 !== 0，你可以选择拿 n % 4 块石头，使得剩余石头数量变成 4 的倍数，从而将对手置于必败局面。

3. 总结

因此，可以总结为：

如果 n % 4 == 0，返回 false。
否则，返回 true。

复杂度分析

时间复杂度：O(1)，只需计算一次模运算。
空间复杂度：O(1)，只使用了常数空间。

代码

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function (n) {
	// 如果 n 不是 4 的倍数，返回 true，否则返回 false
	return n % 4 !== 0;
};

292. Nim 游戏

# 292. Nim 游戏

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

292. Nim 游戏

题目

题目大意

解题思路

复杂度分析

代码

相关题目