Leetcode-cn.com 2022-01-04
🔴 913.cat-and-mouse

🏷️ Tags
#breadth_first_search #graph #memoization #math #dynamic_programming #game_theory

Description
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：


如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。


给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：


如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。



Example

输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0

Leetcode-cn.com 2022-01-20
🟡 2029.stone-game-ix

🏷️ Tags
#greedy #array #math #counting #game_theory

Description
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。


如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。


假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

Example

输入：stones = [2,1]
输出：true
解释：游戏进行如下：
- 回合 1：Alice 可以移除任意一个石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

Leetcode-cn.com 2022-03-22
🟡 2038.remove-colored-pieces-if-both-neighbors-are-the-same-color

🏷️ Tags
#greedy #math #string #game_theory

Description
总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。


如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。
如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。
Alice 和 Bob 不能 从字符串两端删除颜色片段。
如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。


假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

Example

输入：colors = "AAABABB"
输出：true
解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 'A' ，这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。

现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 'B' 的颜色片段 'B' 。
因此，Alice 获胜，返回 true 。

Leetcode-cn.com 2022-05-10
🔴 1728.cat-and-mouse-ii

🏷️ Tags
#breadth_first_search #graph #memoization #math #dynamic_programming #game_theory

Description
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。

它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。


玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。
地板由字符 '.' 表示，玩家可以通过这个格子。
墙用字符 '#' 表示，玩家不能通过这个格子。
食物用字符 'F' 表示，玩家可以通过这个格子。
字符 'C' ， 'M' 和 'F' 在 grid 中都只会出现一次。


猫和老鼠按照如下规则移动：


老鼠 先移动 ，然后两名玩家轮流移动。
每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 grid 。
catJump 和 mouseJump 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。
它们可以停留在原地。
老鼠可以跳跃过猫的位置。


游戏有 4 种方式会结束：


如果猫跟老鼠处在相同的位置，那么猫获胜。
如果猫先到达食物，那么猫获胜。
如果老鼠先到达食物，那么老鼠获胜。
如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。


给你 rows x cols 的矩阵 grid 和两个整数 catJump 和 mouseJump ，双方都采取最优策略，如果老鼠获胜，那么请你返回 true ，否则返回 false 。

 

Example

输入：grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
输出：true
解释：猫无法抓到老鼠，也没法比老鼠先到达食物。

Leetcode-cn.com 2022-05-22
🟡 464.can-i-win

🏷️ Tags
#bit_manipulation #memoization #math #dynamic_programming #bitmask #game_theory

Description
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

Example

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

leetcode.cn 2023-02-22
🟡1140.stone-game-ii

🏷️ Tags
#array #math #dynamic_programming #game_theory

leetcode.com 2023-05-26
🟡1140.stone-game-ii

🏷️ Tags
#array #math #dynamic_programming #game_theory

leetcode.com 2023-05-27
🔴1406.stone-game-iii

🏷️ Tags
#array #math #dynamic_programming #game_theory

leetcode.com 2023-07-28
🟡486.predict-the-winner

🏷️ Tags
#recursion #array #math #dynamic_programming #game_theory

leetcode.com 2023-10-02
🟡2038.remove-colored-pieces-if-both-neighbors-are-the-same-color

🏷️ Tags
#greedy #math #string #game_theory

leetcode.com 2023-11-24
🟡1561.maximum-number-of-coins-you-can-get

🏷️ Tags
#greedy #array #math #game_theory #sorting

leetcode.cn 2024-02-02
🟡1686.stone-game-vi

🏷️ Tags
#greedy #array #math #game_theory #sorting #heap_priority_queue

leetcode.cn 2024-02-03
🟡1690.stone-game-vii

🏷️ Tags
#array #math #dynamic_programming #game_theory

leetcode.cn 2024-02-04
🟢292.nim-game

🏷️ Tags
#brainteaser #math #game_theory

leetcode.cn 2025-09-12
🟡3227.vowels-game-in-a-string

🏷️ Tags
#brainteaser #math #string #game_theory

leetcode.com 2025-09-12
🟡3227.vowels-game-in-a-string

🏷️ Tags
#brainteaser #math #string #game_theory