Leetcode Daily Question

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 。

204 views16:30

CN CN Solution

Leetcode Daily Question

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
解释：猫无法抓到老鼠，也没法比老鼠先到达食物。

217 views16:30

CN CN Solution

Leetcode Daily Question

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