企业官网建设流程全解析

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 <= 100000
• colors仅由字母'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 删除一个 'B'）

Bob 有大量'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)次操作。

例如"BBBBBBB"（L=7）内部可删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'时对称处理（对应实现第 6～13 行）。清零操作保证了跨段不会误累计；
• 每当Acont >= 3（实现第 14～16 行），说明当前这个'A'位于长度不小于 3 的连续段内部、左右邻居均为'A'，Alice 可操作次数加一。这等价于对每段长度为L的'A'连续段贡献L - 2次：当连续计数达到 3、4、…、L 时各计一次；
• Bcont >= 3同理累计 Bob 的操作次数（实现第 17～19 行）；
• 最后返回As > Bs（实现第 21～24 行），完全对应上文推导出的判定条件。

这一实现与 README 中给出的解题思路完全一致（见 题解文档 的"解题思路"一节）：先统计As、Bs，再因 Alice 先手而比较As是否严格大于Bs。

复杂度分析

• 时间复杂度：O(n)，其中n为colors的长度，只需一趟线性扫描；
• 空间复杂度：O(1)，仅使用四个整型变量，与输入规模无关。

在colors.length <= 100000的约束下，该解法单次扫描即可通过，且完全规避了模拟删除（每次删除都要重建字符串、代价可达O(n²)）的陷阱。

边界情况与易错点

1. 连续计数必须跨段清零：Acont/Bcont在遇到对方颜色时必须重置为 0，否则"ABA"中第二个'A'会被误认为属于长度 3 的连续段。
2. 判定用严格大于：As > Bs而非As >= Bs。当双方可操作次数相等时，Bob 完成最后一手，Alice 落败（如"AAAABBBABBB"）。
3. 长度不足 3 的段没有贡献："AA"、"AB"、"A"等输入下As、Bs均为 0，返回false——符合"两端不可删、无中间片段可删"的规则。
4. 不要被"最优策略"迷惑：由于操作不会改变双方总可操作次数，任何合法操作都是"最优操作"，不需要回溯、剪枝或博弈树。

用连续段（run-length）视角再校验

将计数逻辑换成显式的连续段统计，结果完全等价：

• 把colors按相同字符切成连续段；
• 对每个连续段，若长度L >= 3，向对应玩家计数加L - 2；
• 最后比较As > Bs。

两种写法的计数结果一致，读者可以用它作为理解或交叉验证的手段；仓库实际采用的前者写法（边扫描边计数）代码更紧凑，且天然满足O(1)空间。

测试验证：运行用例与回归测试

仓库为该题配置了完整的表驱动测试，见 测试文件：

• 三个官方样例全部覆盖："AAABABB" -> true、"AA" -> false、"ABBBBBBBAAA" -> false（对应测试文件第 27～41 行）；
• 额外增加了一个回归用例"AAAABBBABBB" -> false（测试文件第 43～45 行）：该用例包含两段长度为 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 -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

测试通过fmt.Printf输出每个用例的输入与结果，便于对照推演过程逐条核对。

小结与同类题联想

2038 题的本质是把"带策略的博弈"还原为"确定的计数比较"：由于删除操作不改变局面的可操作性（关键洞察 1），游戏的唯一变数只剩先手顺序，于是判定条件收敛为As > Bs。这类"操作不改变状态量 → 胜负由初始状态决定"的模型，在 LeetCode 中并不少见，例如：

• 877. Stone Game：总石子数为奇数、堆数有限时，先手可保证拿到过半石子，胜负由初始数组唯一确定；
• 810. Chalkboard XOR Game：通过异或与奇偶性在初始状态直接判定胜负，无需模拟过程；
• 292. Nim Game：n % 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