教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「刷穿 LeetCode」系列第No.2038篇的完整技术讲解。该题表面上是 Alice 与 Bob 轮流删除颜色片段的博弈问题但通过观察删除规则的独立性可以将其转化为一次线性扫描统计「可删除的A数量」与「可删除的B数量」并比较大小的脑筋急转弯题。读完本文你将掌握这类「看似博弈、实为计数」问题的识别方法与 O(n) 单遍扫描解法并理解其时间复杂度与空间复杂度的取舍细节。本题在仓库中收录于 Index/脑筋急转弯.md推荐指数 与 Index/模拟.md 两个分类索引下对应题解文件为 LeetCode/2031-2040/2038. 如果相邻两个颜色均相同则删除当前颜色中等.md。题目描述总共有 $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。提示$1 \le colors.length \le 10^5$colors只包含字母A和B示例推演示例 1输入colors AAABABB 输出true解释AAABABB - AABABBAlice 先操作。她删除从左数第二个A这也是唯一一个相邻颜色片段都是A的A。现在轮到 Bob 操作。Bob 无法执行任何操作因为没有相邻位置都是B的颜色片段B。因此Alice 获胜返回true。示例 2输入colors AA 输出false解释Alice 先操作。只有 2 个A且它们都在字符串的两端所以她无法执行任何操作。因此Bob 获胜返回false。示例 3输入colors ABBBBBBBAAA 输出false解释ABBBBBBBAAA - ABBBBBBBAAAlice 先操作。她唯一的选择是删除从右数起第二个A。ABBBBBBBAA - ABBBBBBAA接下来轮到 Bob 操作。他有许多选择他可以选择任何一个B删除。然后轮到 Alice 操作她无法删除任何片段。所以 Bob 获胜返回false。脑筋急转弯删除规则具有独立性这是本题的核心观察也是整个解法的灵魂所在删除任意一个A不会影响可被删除的B的数量反之亦然。为什么我们逐条推敲删除操作只发生在内部位置规则 ③ 禁止删除两端因此删除一个片段后它左右两侧的邻居会变成新的相邻关系。这个邻居变化只发生在被删除片段的两侧只会影响同色片段的连续性判断。Alice 只能删A她删除一个A后改变的是A片段的相邻关系对于B片段而言它们周围的A被移除并不会让某个B多出或失去B邻居——B的邻居里始终只会是B或字符串边界/A而边界与A都不构成相邻两个都是B的条件。更精确地说一个位置i能否被删除只取决于colors[i-1]、colors[i]、colors[i1]三个位置是否同为A对 Alice或同为B对 Bob。删除一个A只会改变其左右两个A位置的邻居构成永远不会改变任何B位置的三元组形态反之亦然。因此两个玩家的可操作次数是完全解耦的记「可删除的A的数量」为 $a$记「可删除的B的数量」为 $b$。由于 Alice 先手且每一轮她只能执行恰好一次删除若 $a b$Alice 的可操作次数严格多于 BobBob 会先无棋可走Alice 获胜若 $a \le b$Bob 的可操作次数不少于 Alice当 Alice 用尽自己的删除机会后轮到 Bob或 Bob 直接耗死 AliceBob 获胜。这里不需要考虑最优策略的博弈选择——因为双方的操作互不干扰可操作总数在开局时就已经被字符串结构唯一确定任何策略都不会改变 $a$ 与 $b$ 的数值胜负在一开始就已注定。这就是本题被称为脑筋急转弯的原因它披着博弈论的外衣内核却是一次简单的计数。单遍扫描实现明确了上述思路后实现就非常直接扫描所有内部位置下标1到n-2只要某个位置与其左右邻居三者同色就计入对应计数。class Solution { public boolean winnerOfGame(String colors) { char[] cs colors.toCharArray(); int n cs.length; int a 0, b 0; for (int i 1; i n - 1; i) { if (cs[i] A cs[i - 1] A cs[i 1] A) a; if (cs[i] B cs[i - 1] B cs[i 1] B) b; } return a b; } }关键实现细节扫描范围i从1到n - 2含因为下标0与n-1是两端规则 ③ 禁止删除它们永远不可能成为被删除者。原文档示例 2 中colors AA之所以 Bob 直接获胜正是因为这个长度为 2 的字符串内部没有任何可扫描的位置。判断条件对每个内部位置i一次性检查cs[i]、cs[i-1]、cs[i1]三个字符是否相同。三个连续的A贡献一次a三个连续的B贡献一次b。计数语义这里的计数对象是可删除的片段个数。需要注意当出现更长的连续同色段如AAAA时中间的两个A各计一次对应两次独立的删除操作这与删除后剩余片段仍可能继续满足条件是自洽的——因为每次删除后剩余部分会重新构成新的三元组但总可操作次数恰好等于初始扫描统计值。这一点也可以反向验证任意连续段长度为 $L$其内部可删除次数为 $\max(0, L - 2)$而逐次删除从中间删恰好能执行这么多步计数与模拟结果一致。复杂度分析时间复杂度$O(n)$其中 $n$ 为字符串长度。只需要一次线性扫描且扫描过程中每个位置只做常数次比较。在 $n \le 10^5$ 的数据范围内这是最优级别的复杂度。空间复杂度使用toCharArray操作会产生一个与原字符串等长的新数组复杂度为 $O(n)$如果改用charAt(i)直接访问字符则可以完全避免额外数组空间复杂度降为 $O(1)$。两种写法在结果上完全等价差别仅在于空间占用。在极限数据规模或对内存敏感的场景下可以优先采用charAt版本class Solution { public boolean winnerOfGame(String colors) { int n colors.length(); int a 0, b 0; for (int i 1; i n - 1; i) { if (colors.charAt(i) A colors.charAt(i - 1) A colors.charAt(i 1) A) a; if (colors.charAt(i) B colors.charAt(i - 1) B colors.charAt(i 1) B) b; } return a b; } }其他语言实现要点本题的解法与语言无关核心就是内部位置 三连字符判断 双计数比较三步。以 Python 为例可以借助切片或直接索引实现同样的逻辑class Solution: def winnerOfGame(self, colors: str) - bool: a b 0 for i in range(1, len(colors) - 1): if colors[i-1] colors[i] colors[i1] A: a 1 elif colors[i-1] colors[i] colors[i1] B: b 1 return a b注意这里使用了elif因为一个位置不可能同时属于A三元组和B三元组用elif可以省去一次无意义的判断原 Java 实现中的两个独立if在语义上同样正确二者等价。边界情况与易错点结合题目约束与示例有几个边界情况值得专门推敲长度不足 3当n 3时如AA、AB、A扫描区间[1, n-2]为空a与b均为 0。此时a b不成立返回false即先手 Alice 必败。这与示例 2 的结论一致——两端不能删长度太短意味着双方都没有任何操作空间。字符串两端不可删colors[0]与colors[n-1]即使满足左右邻居同色实际两端只有一个邻居也不参与计数因此扫描区间必须严格排除两端。原文档示例 3 中 Alice 唯一能删的A是从右数起第二个正是因为最右侧的A位于端点。胜负判定方向只有当a b时 Alice 获胜a b时同样是 Bob 获胜——因为 Alice 先手双方可操作次数相等时轮到 Alice 时她已经没有棋可走。这是最容易被忽略的细节严格大于而非大于等于。连续段长度与可删次数的关系任意长度为 $L$ 的连续同色段贡献的可删除次数为 $\max(0, L - 2)$。例如AAA贡献 1 次、AAAA贡献 2 次、AAAAA贡献 3 次。这个结论可以直接验证单遍扫描的计数正确性也可作为面试时快速口算的工具。为什么最优策略不影响结论本题题干强调假设 Alice 和 Bob 都采用最优策略。常规博弈题如 Index/博弈论.md 分类下的题目需要借助必胜态/必败态递推甚至 SG 函数但本题不同删除A不影响B的可删性删除B也不影响A的可删性因此双方的可操作总次数 $a$ 与 $b$ 在游戏开始前就是不变量任何策略都无法改变对方可操作次数的多寡游戏过程唯一确定的结果就是操作次数多的一方获胜。所谓最优策略在这里退化成了每次有得删就删不存在真正的策略博弈空间。这也是本题被归入脑筋急转弯而非博弈论分类的根本原因识别出问题本质是计数而非博弈是解出本题的关键一步。相关题目索引本题同时收录在仓库的两个算法分类索引中可对照学习同类题型Index/脑筋急转弯.md收录路径交叉、根据身高重建队列、灯泡开关 Ⅱ、所有蚂蚁掉下来前的最后一刻等「脑筋急转弯」类题目本题推荐指数为 是该分类下的代表作之一Index/模拟.md收录可通过模拟过程直接推导结论的题目本题同样适用。若希望进一步理解计数替代模拟的思想可对比同索引下的 1503. 所有蚂蚁掉下来前的最后一刻蚂蚁相遇可视为穿透本质是将复杂模拟转化为简单计数的另一经典案例。系列说明本文为「刷穿 LeetCode」系列文章的第No.2038篇。该系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题系列优先将不带锁的题目全部刷完。在该系列文章里除了讲解解题思路以外还会尽可能给出最为简洁的代码如果涉及通解还会给出相应的代码模板。所有系列文章的题解、代码与 LeetCode 原题均可在本仓库LogicStack-LeetCode中查看按题号分目录存放于 LeetCode 目录下例如本题位于 LeetCode/2031-2040 目录。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐答案不在最像的那份文档里GraphRAG 多跳检索完整指南答案不在最像的那份文档里GraphRAG 多跳检索完整指南 当 RAG 只检索到一份文档、LLM 却自信地答错时问题往往不在模型而在检索层。Semanti语音AI 应用深度学习宫水三叶的刷题日记LeetCode 1588 所有奇数长度子数组的和——前缀和与数学组合计数双解法实战宫水三叶的刷题日记LeetCode 1588 所有奇数长度子数组的和——前缀和与数学组合计数双解法实战 导读 本文基于 LogicStack LeetCode教程文档stylelint 规则详解hue-degree-notation —— 统一颜色色相的度数与数字表示法stylelint 规则详解hue degree notation —— 统一颜色色相的度数与数字表示法 本篇技术指南围绕 stylelint 内置规则 hu代码质量静态分析前端上一篇AMD Ryzen调试工具SMUDebugTool深入浅出从一次蓝屏到安全降压老手的完整历程下一篇网易云音乐ncm转mp3全攻略ncmdumpGUI一键批量转换完整上手教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考