# LeetCode Problem 2038: 如果相邻两个颜色均相同则删除当前颜色 (Winner of the Game)
LeetCode Problem 2038: 如果相邻两个颜色均相同则删除当前颜色 (Winner of the Game)
在本篇博客中,我们将深入探讨 LeetCode 第2038题——如果相邻两个颜色均相同则删除当前颜色。该问题涉及字符串处理与游戏策略,旨在考察如何在给定规则下判断游戏的胜负。我们将详细解析问题、探索解决方案,并通过代码示例展示如何实现这一逻辑。
问题描述
背景
给定一个由 'A' 和 'B' 组成的字符串 colors,每个字符代表一个颜色片段。Alice 和 Bob 在玩一个游戏,他们轮流从字符串中删除颜色。Alice 先手。
游戏规则
-
删除规则:
- Alice 可以删除一个
'A',条件是该'A'的相邻两个颜色片段也都是'A'。 - Bob 可以删除一个
'B',条件是该'B'的相邻两个颜色片段也都是'B'。
- Alice 可以删除一个
-
限制:
- 无法删除位于字符串两端的颜色片段,因为它们没有两个相邻的颜色片段。
- 每次删除一个颜色片段后,字符串会重新连接,新的相邻关系会重新建立。
-
胜负判定:
- 如果一方无法进行删除操作,则该玩家输掉游戏,另一方获胜。
- 假设 Alice 和 Bob 都采用最优策略,判断 Alice 是否获胜。
示例
示例 1
输入: colors = "AAABABB"
输出: true
解释:
- Alice 删除中间的 'A',字符串变为 "AABABB"。
- Bob 无法进行删除操作,因为没有三个连续的 'B'。
- Alice 获胜。
示例 2
输入: colors = "AA"
输出: false
解释:
- Alice 无法进行删除操作,因为字符串长度不足。
- Bob 获胜。
示例 3
输入: colors = "ABBBBBBBAAA"
输出: false
解释:
- Alice 删除最后的 'A',字符串变为 "ABBBBBBBAA"。
- Bob 删除一个 'B',字符串变为 "ABBBBBBAA"。
- Alice 无法进行删除操作。
- Bob 获胜。
提示
1 <= colors.length <= 10^5colors只包含字母'A'和'B'
解决方案
要判断 Alice 是否能获胜,我们需要计算 Alice 和 Bob 各自能进行多少次删除操作,然后比较两者的次数。
关键观察
- 连续字符的分组:对于连续的
'A'或'B',计算其长度。 - 可删除次数:对于每一组连续的字符,只有当长度大于等于3时,才能进行删除操作。具体的删除次数为
长度 - 2。- 例如,连续5个
'A',Alice 可以进行5 - 2 = 3次删除。
- 例如,连续5个
- 总删除次数:
- Alice 的总删除次数为所有连续
'A'组的(长度 - 2)之和。 - Bob 的总删除次数为所有连续
'B'组的(长度 - 2)之和。
- Alice 的总删除次数为所有连续
- 胜负判定:如果 Alice 的删除次数大于 Bob 的删除次数,则 Alice 获胜,返回
true;否则,返回false。
算法步骤
- 初始化两个计数器
alice_moves和bob_moves分别记录 Alice 和 Bob 的可删除次数。 - 遍历字符串
colors,统计连续'A'和'B'的长度。 - 对于每个连续的
'A'或'B'组,计算其可删除次数,并累加到相应的计数器。 - 最后比较
alice_moves和bob_moves的值,判断 Alice 是否获胜。
复杂度分析
- 时间复杂度:O(n),其中 n 是字符串
colors的长度。我们只需遍历一次字符串。 - 空间复杂度:O(1),仅使用了常数级别的额外空间。
代码实现
以下是基于上述思路的 Python 实现:
class Solution:def winnerOfGame(self, colors: str) -> bool:alice_moves = 0bob_moves = 0n = len(colors)i = 0while i < n:current_char = colors[i]count = 1# 统计当前字符连续出现的次数while i + 1 < n and colors[i + 1] == current_char:count += 1i += 1# 如果连续字符数大于等于3,计算可删除次数if count >= 3:if current_char == 'A':alice_moves += count - 2else:bob_moves += count - 2i += 1# Alice 必须有比 Bob 更多的删除次数才能获胜return alice_moves > bob_moves
代码解析
-
初始化:
alice_moves = 0 bob_moves = 0 n = len(colors) i = 0alice_moves和bob_moves分别记录 Alice 和 Bob 的可删除次数。n是字符串的长度,i是当前遍历的索引。
-
遍历字符串:
while i < n:current_char = colors[i]count = 1# 统计当前字符连续出现的次数while i + 1 < n and colors[i + 1] == current_char:count += 1i += 1# 如果连续字符数大于等于3,计算可删除次数if count >= 3:if current_char == 'A':alice_moves += count - 2else:bob_moves += count - 2i += 1- 对于每一个字符,统计其连续出现的次数
count。 - 如果
count >= 3,则根据字符类型增加相应的删除次数。 - 最后,移动到下一个不同的字符。
- 对于每一个字符,统计其连续出现的次数
-
胜负判断:
return alice_moves > bob_moves- 如果 Alice 的删除次数大于 Bob 的,则 Alice 获胜,返回
true;否则,返回false。
- 如果 Alice 的删除次数大于 Bob 的,则 Alice 获胜,返回
示例运行
让我们通过几个示例来验证我们的算法。
示例 1
colors = "AAABABB"
solution = Solution()
print(solution.winnerOfGame(colors)) # 输出: True
解析:
- 连续
'A'的组:'AAA',可删除次数为3 - 2 = 1。 - 连续
'B'的组:'B'、'BB',均不足3个,不可删除。 - Alice 的删除次数
1,Bob 的删除次数0。 - 因为
1 > 0,Alice 获胜。
示例 2
colors = "AA"
solution = Solution()
print(solution.winnerOfGame(colors)) # 输出: False
解析:
- 连续
'A'的组:'AA',不足3个,不可删除。 - Alice 的删除次数
0,Bob 的删除次数0。 - 因为
0不是大于0,Alice 无法获胜。
示例 3
colors = "ABBBBBBBAAA"
solution = Solution()
print(solution.winnerOfGame(colors)) # 输出: False
解析:
- 连续
'A'的组:'A'、'AAA',可删除次数为1。 - 连续
'B'的组:'BBBBBBB',可删除次数为7 - 2 = 5。 - Alice 的删除次数
1,Bob 的删除次数5。 - 因为
1小于5,Bob 获胜。
总结
我们了解到如何通过统计连续字符的数量来判断 Alice 和 Bob 各自的删除次数。关键在于识别连续的 'A' 和 'B' 组,并根据规则计算可删除次数。最终,通过比较两者的删除次数,我们可以高效地判断游戏的胜负。
相关文章:
# LeetCode Problem 2038: 如果相邻两个颜色均相同则删除当前颜色 (Winner of the Game)
LeetCode Problem 2038: 如果相邻两个颜色均相同则删除当前颜色 (Winner of the Game) 在本篇博客中,我们将深入探讨 LeetCode 第2038题——如果相邻两个颜色均相同则删除当前颜色。该问题涉及字符串处理与游戏策略,旨在考察如何在给定规则下判断游戏的…...
Redis面试相关
Redis开篇 使用场景 缓存 缓存穿透 解决方法一: 方法二: 通过多次hash来获取对应的值。 小结 缓存击穿 缓存雪崩 打油诗 双写一致性 两种不同的要求 强一致 读锁代码 写锁代码 强一致,性能低。 延迟一致 方案一:消息队列 方…...
4.CSS文本属性
4.1文本颜色 div { color:red; } 属性值预定义的颜色值red、green、blue、pink十六进制#FF0000,#FF6600,#29D794RGB代码rgb(255,0,0)或rgb(100%,0%,0%) 4.2对齐文本 text-align 属性用于设置元素内文本内容的水平对齐方式。 div{ text-align:center; } 属性值解释left左对齐ri…...
Mongo高可用架构解决方案
Mongo主从复制哪些事(仅适用特定场景) 对数据强一致性要求不高的场景,一般微服务架构中不推荐 master节点可读可写操作,当数据有修改时,会将Oplog(操作日志)同步到所有的slave节点上。那么对于从节点来说仅只读,所有slave节点从master节点同步数据,然而从节点之间互相…...
Rabbitmq 业务异常与未手动确认场景及解决方案
消费端消费异常,业务异常 与 未手动确认是不是一个场景,因为执行完业务逻辑,再确认。解决方案就一个,就是重试一定次数,然后加入死信队列。还有就是消费重新放入队列,然后重新投递给其他消费者,…...
linux,centos7.6安装禅道
1.cd /opt 2.wget https://www.zentao.net/dl/zentao/18.5/ZenTaoPMS.18.5.zbox_64.tar.gz 3.tar xvzf ZenTaoPMS.18.5.zbox_64.tar.gz 4./opt/zbox/zbox --aport 4005 --mport 3307 start 安全组开启一下两个端口 –aport 4005:设置Apache启动端口为4005 –mport 3…...
java基础之代理
代理模式(Proxy Pattern) 简介 是一种结构型设计模式,主要用于为某对象提供一个代理对象,以控制对该对象的访问。通过引入一个代理对象来控制对原对象的访问。代理对象在客户端和目标对象之间充当中介,负责将客户端的…...
计算机网络——期末复习(6)期末考试样例2(含答案)
一、单项选择题(每题1分,共10小题,共计10分) 1.因特网多播采用的管理协议是( )协议。 A.UDP B.BGP C.IGMP D.TCP 2.采用CIDR时,某计算机的IP地址是202.35.79.88/19,该计算机所处子网的地址是( )。 A.202.35.0.…...
JavaScript 获取DOM对象
html的标签被js获取到之后就变成了js对象,对象里面包含了标签的属性和方法 。同一时间获取多个对象则会翻译一个数组,数组元素是对象 获取方法 1. const a document.getElementById("id"),根据标签的id来获取。因为id是唯一的、…...
一文讲明白朴素贝叶斯算法及其计算公式(入门普及)
1、贝叶斯算法 贝叶斯定理由英国数学家托马斯贝叶斯 ( Thomas Bayes) 提出的,用来描述两个条件概率之间的关系。通常,事件A在事件B 发生的条件下与事件 B 在事件 A 发生的条件下,它们两者的概率并不相同,但是它们两者之间存在一定…...
实际开发中,常见pdf|word|excel等文件的预览和下载
实际开发中,常见pdf|word|excel等文件的预览和下载 背景相关类型数据之间的转换1、File转Blob2、File转ArrayBuffer3、Blob转ArrayBuffer4、Blob转File5、ArrayBuffer转Blob6、ArrayBuffer转File 根据Blob/File类型生成可预览的Base64地址基于Blob类型的各种文件的下载各种类型…...
Python自学 - 递归函数
1 Python自学 - 递归函数 递归函数是一种在函数体内调用自己的函数,就像“左脚踩着右脚,再右脚踩着左脚… 嗯,你就可以上天了!”。递归函数虽然不能上天,但在处理某些场景时非常好用, 一种典型的场景就是遍…...
Spark-Streaming有状态计算
一、上下文 《Spark-Streaming初识》中的NetworkWordCount示例只能统计每个微批下的单词的数量,那么如何才能统计从开始加载数据到当下的所有数量呢?下面我们就来通过官方例子学习下Spark-Streaming有状态计算。 二、官方例子 所属包:org.…...
Markdown如何导出Html文件Markdown文件
Markdown如何导出Html文件Markdown文件 前言语法详解小结其他文章快来试试吧☺️ Markdown 导出 HTML 👈点击这里也可查看 前言 Markdown的源文件以md为后缀。Markdown是HTML语法的简化版本,它本身不带有任何样式信息。我们所看到的Markdown网页(如&…...
使用Python进行图像裁剪和直方图分析
一、简介 在数字图像处理领域,裁剪和分析图像的直方图是两个非常基本且重要的操作。本文将通过一个简单的Python项目,展示如何使用skimage和matplotlib库来裁剪图像并分析其RGB通道的直方图。 二、环境准备 在开始之前,请确保你已经安装了以…...
企业内管信息化系统
本文结尾处获取源码。 本文结尾处获取源码。 本文结尾处获取源码。 一、相关技术 后端:Java、JavaWeb / Springboot。前端:Vue、HTML / CSS / Javascript 等。数据库:MySQL 二、相关软件(列出的软件其一均可运行) I…...
【python因果库实战15】因果生存分析4
这里写目录标题 加权标准化生存分析总结个体层面的生存曲线 加权标准化生存分析 我们还可以将加权与标准化结合起来,使用 WeightedStandardizedSurvival 模块。在这里,我们将逆倾向得分加权模型(根据基线协变量重新加权人群)与加…...
Linux 线程详解
目录 一、线程概述 二、线程创建 三、线程终止 四、线程回收 五、线程取消 六、线程分离 七、线程安全 一、线程概述 线程是进程内的一个执行单元,是进程内可调度的实体。一个进程可以包含多个线程,这些线程共享进程的资源,如内存空…...
云架构:考量与框架
云架构:考量与框架 引言 在当今的数字化环境中,云计算已成为现代商业运营的基石。一个设计良好的云架构框架为可扩展、安全和弹性的系统奠定了基础。本文将深入探讨云架构的核心要素,讨论重要的考量因素、设计指南,以及最佳实践…...
SD下载、安装、使用、卸载-Stable Diffusion整合包v4.10发布!
目录 前言概述 SD安装1、安装软件2、启动3、配置4、运行5、测试 导入SD模型【决定画风】常用模型下载安装模型 SD卸载SD文生图提示词提示词使用技巧提示词的高级使用技巧强调关键词 前言 我向来不喜欢搞一些没有用的概念,所以直接整理可能用到的东西。 sd简单的说…...
Novel-Downloader:200+网站小说下载终极指南,高效实现离线阅读
Novel-Downloader:200网站小说下载终极指南,高效实现离线阅读 【免费下载链接】novel-downloader 一个可扩展的通用型小说下载器。 项目地址: https://gitcode.com/gh_mirrors/no/novel-downloader 你是否曾经遇到过这样的情况:正在追…...
终极Windows软件清理指南:Bulk Crap Uninstaller完整使用教程
终极Windows软件清理指南:Bulk Crap Uninstaller完整使用教程 【免费下载链接】Bulk-Crap-Uninstaller Remove large amounts of unwanted applications quickly. 项目地址: https://gitcode.com/gh_mirrors/bu/Bulk-Crap-Uninstaller Bulk Crap Uninstaller…...
Mac Mouse Fix终极指南:重构macOS鼠标体验的完整解决方案
Mac Mouse Fix终极指南:重构macOS鼠标体验的完整解决方案 【免费下载链接】mac-mouse-fix Mac Mouse Fix - Make Your $10 Mouse Better Than an Apple Trackpad! 项目地址: https://gitcode.com/GitHub_Trending/ma/mac-mouse-fix 在macOS生态系统中&#x…...
终极指南:3步为Windows 11 LTSC系统快速安装微软商店应用商店
终极指南:3步为Windows 11 LTSC系统快速安装微软商店应用商店 【免费下载链接】LTSC-Add-MicrosoftStore Add Windows Store to Windows 11 24H2 LTSC 项目地址: https://gitcode.com/gh_mirrors/ltscad/LTSC-Add-MicrosoftStore Windows 11 LTSC-Add-Micros…...
配方法在二次型标准化中的可逆线性变换机制解析
1. 配方法为何总能找到可逆变换 二次型标准化问题就像给一个复杂的多项式方程"瘦身",而配方法就是最直观的"减肥教练"。许多初学者会疑惑:为什么通过配方总能找到那个关键的线性变换矩阵?这背后其实藏着线性代数的一个精…...
如何打造优雅的浮动标签文本字段:SkyFloatingLabelTextField核心实现原理详解
如何打造优雅的浮动标签文本字段:SkyFloatingLabelTextField核心实现原理详解 【免费下载链接】SkyFloatingLabelTextField A beautiful and flexible text field control implementation of "Float Label Pattern". Written in Swift. 项目地址: https…...
别再手动reshape了!用einops.rearrange优雅处理PyTorch张量(附实战代码)
用einops.rearrange重塑PyTorch张量操作:告别混乱的维度变换 在深度学习项目中,张量维度操作就像乐高积木的拼接重组——我们总需要把数据块拆开、旋转、重新组合。但当你面对view()、permute()和reshape()的嵌套调用时,代码往往会变成难以维…...
T536主板的UART功能(RS232/RS485)的使用-盈鹏飞嵌入式
CoM-T536产品特性:采用Allwinner公司Cortex-A55四核T536处理器,最高速度为1.6GHZ;支持2TOPS NPU,仅特定型号支持;支持4K/25fps H.264视频编码,支持4K/15fps MJPEG编码;支持1-4G Bytes LPDDR4 SDRAM…...
高效脚本编写:用Codex告别重复造轮子
技术文章大纲:告别重复造轮子——Codex写脚本的高效实践引言:自动化脚本的意义与Codex的潜力重复性工作的痛点与脚本的价值OpenAI Codex在代码生成领域的突破性能力本文目标:如何利用Codex快速生成实用脚本Codex基础:理解其工作原…...
2025届学术党必备的降重复率方案推荐榜单
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 要降低AIGC检测率,需从文本特征着手。首先,得对词汇多样性予以调整&…...
