LeetCode 2038 题解Remove Colored Pieces if Both Neighbors are the Same Color | LeetCode-Go 贪心计数实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 2038 题「Remove Colored Pieces if Both Neighbors are the Same Color」如果相邻两个颜色均相同则删除当前颜色展开完整讲解题目规则、官方示例推演、核心贪心计数思路与 Go 实现。文中给出的解法来自 LeetCode-Go 仓库的 2038 题解目录读者学完可以掌握一类博弈化简为计数的思维模型当每一步操作都不改变后续局面状态时博弈胜负只取决于双方可操作次数的比较无需模拟。题目背景与游戏规则总共有n个颜色片段排成一列每个片段要么是A要么是B。给定长度为n的字符串colors其中colors[i]表示第i个片段的颜色。Alice 和 Bob 玩一个轮流删除片段的游戏Alice 先手规则如下Alice 只能删除一个相邻两个片段都是A的A片段不能删除B片段Bob 只能删除一个相邻两个片段都是B的B片段不能删除A片段两人都不能删除位于字符串两端的片段轮到某位玩家时若无法操作该玩家输掉游戏另一方获胜。假设两人都采取最优策略若 Alice 获胜返回true否则返回false。约束条件1 colors.length 100000colors仅由字母A和B组成题目要求O(n)级别的解法数据规模达到十万因此不能用状态模拟、BFS/DFS 等重型手段必须寻找轻量化的判定方法。官方示例推演示例 1输入: colors AAABABB 输出: true推演过程AAABABB - AABABB。Alice 先手唯一可操作的是左起第二个A其左右邻居都是A。删除后轮到 Bob此时不存在两个邻居都是B的B片段Bob 无法操作而落败Alice 获胜。示例 2输入: colors AA 输出: false只有两个A且都处于字符串边缘Alice 首回合即无法操作Bob 获胜。示例 3输入: colors ABBBBBBBAAA 输出: false推演过程ABBBBBBBAAA - ABBBBBBBAA Alice 删除右起第二个 A ABBBBBBBAA - ABBBBBBAA Bob 删除一个 BBob 有大量B可以删除Alice 在第二轮已无A可删Bob 获胜。核心思路把博弈化简为计数问题关键洞察 1任意一次删除都不会改变后续的可操作数量这是本题最重要的观察。假设 Alice 删除一个满足条件的A例如从AAA中删掉中间那个变成AA被删除的A的左右邻居都是A删除后剩余的A片段及其相邻关系不受影响只是连续段的长度减一所有B片段的位置与相邻关系完全不变Bob 的可操作数量不变。同理Bob 删除B也不会影响 Alice 的可操作数量。因此无论双方以什么顺序、删哪个片段双方总可操作次数在整个游戏过程中是固定不变的常量。游戏变成了一盘手牌数量固定、回合强制进行的棋没有任何决策能改变局面走向只有先手优势是变量。关键洞察 2连续段的长度直接决定可操作次数对于一个长度为L的连续相同字符段run只有内部的片段才可能被删除即去掉两端的L - 2个每次删除内部一个片段连续段长度减一只要长度仍大于等于 3就还能继续删因此该连续段总共可贡献max(0, L - 2)次操作。例如BBBBBBBL7内部可删7 - 2 5次这与示例 3 中 Bob 的可操作数一致。关键洞察 3先手优势与胜负判定设As为 Alice 的总可操作次数Bs为 Bob 的总可操作次数As Bs是游戏的总回合数。Alice 先手意味着她占据第 1、3、5……回合。由于回合是强制进行的只要轮到自己有操作就必须操作游戏结束于某一方无法操作时若As Bs总回合为奇数个Alice 完成最后一次操作后轮到 Bob 无牌可出Alice 获胜若As Bs总回合为偶数个或双方都无操作Bob 走完最后一回合后 Alice 无牌可出Bob 获胜。所以判定条件极其简洁As Bs时返回true否则返回false。注意是比较后返回As Bs的布尔值本身As Bs时 Alice 同样落败示例 2 的AA就是As Bs 0的情形。Go 实现与逐行解读仓库 2038 题解目录 下的 实现文件 中winnerOfGame采用单次线性扫描完成计数package leetcode func winnerOfGame(colors string) bool { As, Bs : 0, 0 Acont, Bcont : 0, 0 for _, color : range colors { if color A { Acont 1 Bcont 0 } else { Bcont 1 Acont 0 } if Acont 3 { As } if Bcont 3 { Bs } } if As Bs { return true } return false }逐段解读As、Bs分别累计 Alice、Bob 的可操作次数Acont、Bcont是当前正在扫描的连续段长度遇到A时Acont加一并将Bcont清零遇到B时对称处理对应实现第 613 行。清零操作保证了跨段不会误累计每当Acont 3实现第 1416 行说明当前这个A位于长度不小于 3 的连续段内部、左右邻居均为AAlice 可操作次数加一。这等价于对每段长度为L的A连续段贡献L - 2次当连续计数达到 3、4、…、L 时各计一次Bcont 3同理累计 Bob 的操作次数实现第 1719 行最后返回As Bs实现第 2124 行完全对应上文推导出的判定条件。这一实现与 README 中给出的解题思路完全一致见 题解文档 的解题思路一节先统计As、Bs再因 Alice 先手而比较As是否严格大于Bs。复杂度分析时间复杂度O(n)其中n为colors的长度只需一趟线性扫描空间复杂度O(1)仅使用四个整型变量与输入规模无关。在colors.length 100000的约束下该解法单次扫描即可通过且完全规避了模拟删除每次删除都要重建字符串、代价可达O(n²)的陷阱。边界情况与易错点连续计数必须跨段清零Acont/Bcont在遇到对方颜色时必须重置为 0否则ABA中第二个A会被误认为属于长度 3 的连续段。判定用严格大于As Bs而非As Bs。当双方可操作次数相等时Bob 完成最后一手Alice 落败如AAAABBBABBB。长度不足 3 的段没有贡献AA、AB、A等输入下As、Bs均为 0返回false——符合两端不可删、无中间片段可删的规则。不要被最优策略迷惑由于操作不会改变双方总可操作次数任何合法操作都是最优操作不需要回溯、剪枝或博弈树。用连续段run-length视角再校验将计数逻辑换成显式的连续段统计结果完全等价把colors按相同字符切成连续段对每个连续段若长度L 3向对应玩家计数加L - 2最后比较As Bs。两种写法的计数结果一致读者可以用它作为理解或交叉验证的手段仓库实际采用的前者写法边扫描边计数代码更紧凑且天然满足O(1)空间。测试验证运行用例与回归测试仓库为该题配置了完整的表驱动测试见 测试文件三个官方样例全部覆盖AAABABB - true、AA - false、ABBBBBBBAAA - false对应测试文件第 2741 行额外增加了一个回归用例AAAABBBABBB - false测试文件第 4345 行该用例包含两段长度为 3 的B和一段长度为 4 的A正确结果是As Bs 2而判负注释明确指出旧的错误实现会把它误判为true用于防止计数或比较逻辑回归出错。在仓库根目录下可以用以下命令单独运行本题测试依赖 go.mod 声明的模块与 Go 1.19 环境go test -v -run Test_Problem2038 ./leetcode/2038.Remove-Colored-Pieces-if-Both-Neighbors-are-the-Same-Color/如需跑全量 LeetCode 用例并生成覆盖率报告仓库提供了 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...测试通过fmt.Printf输出每个用例的输入与结果便于对照推演过程逐条核对。小结与同类题联想2038 题的本质是把带策略的博弈还原为确定的计数比较由于删除操作不改变局面的可操作性关键洞察 1游戏的唯一变数只剩先手顺序于是判定条件收敛为As Bs。这类操作不改变状态量 → 胜负由初始状态决定的模型在 LeetCode 中并不少见例如877. Stone Game总石子数为奇数、堆数有限时先手可保证拿到过半石子胜负由初始数组唯一确定810. Chalkboard XOR Game通过异或与奇偶性在初始状态直接判定胜负无需模拟过程292. Nim Gamen % 4 ! 0即可判定先手必胜。刷题时遇到两人轮流操作、问谁必胜的题目可以先问自己三个问题操作是否改变对方的可操作数总操作次数是否固定先手优势如何体现若第一个问题答案为否那么大概率可以像本题一样用一趟线性扫描把博弈化简成计数拿到O(n)时间、O(1)空间的优雅解法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
