用匠心精神解决LeetCode第726题原子的数量

embedded/2024/11/22 1:10:06/
726.原子的数量

难度:困难

问题描述:

给你一个字符串化学式formula,返回每种原子的数量。

原子总是以一个大写字母开始,接着跟随0个或任意个小写字母,表示原子的名字。

如果数量大于1,原子后会跟着数字表示原子的数量。如果数量等于1则不会跟数字。

例如,"H2O"和"H2O2"是可行的,但"H1O2"这个表达是不可行的。

两个化学式连在一起可以构成新的化学式。

例如"H2O2He3Mg4"也是化学式。

由括号括起的化学式并佐以数字(可选择性添加)也是化学式。

例如"(H2O2)"和"(H2O2)3"是化学式。

返回所有原子的数量,格式为:第一个(按字典序)原子的名字,跟着它的数量(如果数量大于1),然后是第二个原子的名字(按字典序),跟着它的数量(如果数量大于1),以此类推。

示例1:

输入:formula="H2O"

输出:"H2O"

解释:原子的数量是{'H':2,'O':1}。

示例2:

输入:formula="Mg(OH)2"

输出:"H2MgO2"

解释:原子的数量是{'H':2,'Mg':1,'O':2}。

示例3:

输入:formula="K4(ON(SO3)2)2"

输出:"K4N2O14S4"

解释:原子的数量是{'K':4,'N':2,'O':14,'S':4}。

提示:

1<=formula.length<=1000

formula由英文字母、数字、'('和')'组成

formula总是有效的化学式

问题分析及解决思路:

为了使问题处理更加简便,对化学式中原子符号是两个或两个以上字母的,用原子符号大写字母之后的第一个小写字母进行替换,这样简化成每一个原子都只用一个字母代表,在处理完成之后,再替换回原来的原子符号

刚开始,我认为只要对原始字符串formula一层层去括号,括号去完之后,再将数字转换为相应数量的原子字符,最后再统计各原子的数量,整理得到题目要求的结果。比如形如(AB)2(CD(EF)2)2(CD)2这样的化学式,其处理步骤如下:

(AB)2(CD(EF)2)2(CD)2--->ABABCD(EF)2CD(EF)2CDCD---->ABABCDEFEFCDEFEFCDCD--->统计各原子个数--->A2B2C4D4E4F4

结果发现把最外层的括号一次性全部去掉的处理使问题变得较为复杂

其实,可以使处理更加简便单纯,每次只处理第一个括号,处理完成后再处理新生成的字符串的第一个括号,直到字符串中没有括号为止。比如上面的化学式,可以这样处理:

(AB)2(CD(EF)2)2(CD)2--->ABAB(CD(EF)2)2(CD)2--->ABABCD(EF)2CD(EF)2(CD)2--->ABABCDEFEFCD(EF)2(CD)2--->ABABCDEFEFCDEFEF(CD)2--->ABABCDEFEFCDEFEFCDCD--->统计各原子个数--->A2B2C4D4E4F4

其实,这种简化处理印证了一种思维,函数功能尽量简单单纯,不要复杂,这样使程序的可读性变强,处理思路更加清晰,功能更加容易实现,正如python之禅所说:Simple is better than complex.

根据上面的处理思路,设计了如下一些函数来处理:

  1. 函数fposition(s),功能是对字符串s,寻找第一个括号的起始位置和结束位置的索引号,并返回
  2. 函数getnum(s,end),功能是根据字符串s中括号的结束位置end,找到其后所跟数字并返回,如果没有数字或括号的结束位置已经处于s的结尾,则返回1
  3. 函数clyc(s),功能是对字符串s找到第一个括号的起始位置和结束位置,并根据结束位置找到其后的数字,将数字作用于括号中的字符处理的结果字符串返回
  4. 函数nposition(s),功能为查找字符串s中数字出现的索引号,如果没有数字,返回0,这个函数配合getnum(s,end)函数,是在将字符串中的括号处理完之后,只剩下字母和数字的情况下使用的
  5. 函数lastcl(s),功能是对已经处理完括号的字符串s进行数字的反复处理,返回一个没有数字的字符串
  6. 函数find2atom(s),功能将原子符号是两个或两以上的找出,并以列表形式返回

程序如下:
python">#在字符串s中找到第一个括号的起始位置和对应的结束位置并返回
def fposition(s):n=len(s)k=0start=0end=0for i in range(n):if s[i]=='(':if k==0:start=ik=k+1elif s[i]==')':k=k-1if k==0:end=ibreakreturn start,end#在字符串s中根据右括号的位置end找到在其右的数字并返回,如果没有数字或已经处于s的结尾,返回1
def getnum(s,end):n=len(s)if end==n-1 or end<n-1 and not s[end+1].isnumeric():return 1else:for i in range(end+1,n):if s[i].isnumeric():continueelse:return int(s[end+1:i])else:return int(s[end+1:])#对字符串s根据括号和其后的数字进行一次处理,并返回处理之后的字符串
def clyc(s):n=len(s)start,end=fposition(s)num=getnum(s,end)s1=s[:start]s2=s[start+1:end]*numk=end+len(str(num))if k==n-1:s3=''else:s3=s[k+1:]return s1+s2+s3#返回字符串s中第一个数字的位置,如果没有数字,返回0
def nposithon(s):n=len(s)for i in range(n):if s[i].isnumeric():return ielse:return 0#对已经处理完括号的字符串s按其中的数字反复处理,返回一个没有数字的字符串
def lastcl(s):i=nposithon(s)while i!=0:n = getnum(s, i-1)s1=s[:i-1]s2=s[i-1]*ns3=s[i+len(str(n)):]s=s1+s2+s3i=nposithon(s)return s#查找并返回字符串s中含有两个或两个以上字母的原子
def find2atom(s):a=[]n=len(s)k=0start=0for i in range(n):if s[i].islower():if k==0:start=i-1k=k+1else:if k!=0:a.append(s[start:i])start=0k=0else:continueif k!=0:a.append(s[start:])return a#主程序
formula=input('pls input formula=')#查找formula中包含两个或两个以上字母的原子
a=find2atom(formula)# 对formula中有两个或两个以上字母的原子用该原子的第一个小写字母替换
for i in a:formula=formula.replace(i,i[1])#去掉所有括号
while '(' in formula:formula=clyc(formula)#处理数字,变成无数字字符的字符串
s=lastcl(formula)#统计各字符的个数并按字典顺序重新合成新的字符串
d=list(set(list(s)))
e=[]
for i in d:c=s.count(i)e.append([i,str(c) if c>1 else ''])#将替换为小写字母的原子替换回原来多个字母形式的原子符号
for i in e:for j in a:if i[0]==j[1]:i[0]=j#按字典序排序
e.sort(key=lambda x:x[0])#组合成最终结果并输出
s=''.join(list(map(lambda x:''.join(x),e)))
print(s)

运行实例一

pls input formula=Mg(OH)2

H2MgO2

运行实例二

pls input formula=(AB)2(CD(EF)2)2(CD)2

A2B2C4D4E4F4

运行实例三

pls input formula=K4(ON(SO3)2)2

K4N2O14S4

运行实例四

pls input formula=Aggg3(Cu(OH)2)2(NaOH)2

Aggg3Cu2H6Na2O6

感悟:

编程犹如雕刻,雕刻用雕刀雕出精美的艺术品,独具匠心,编程则用编程语言和算法思想对问题抽丝剥茧,可谓匠心独运。要提高技艺,都需要反复练习,或心细如发,或大巧若拙,熟能生巧,方能形成智慧的结晶。


http://www.ppmy.cn/embedded/139478.html

相关文章

云计算虚拟化-kvm创建虚拟机

作者介绍&#xff1a;简历上没有一个精通的运维工程师。希望大家多多关注作者&#xff0c;下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 虚拟化&#xff0c;简单来说就是把一台服务器/PC电脑&#xff0c;虚拟成多台独立的虚拟机&#xff0c;每台虚拟机之间相互隔…

【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响

【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响 论文&#xff1a;https://arxiv.org/pdf/2310.05492 目录 文章目录 【大语言模型】ACL2024论文-12 大型语言模型的能力如何受到监督式微调数据组成影响论文&#xff1a;https://arxiv.org/p…

sql中的聚合函数

SQL中的聚合函数用于对表中的数据进行汇总计算&#xff0c;常用来生成统计信息&#xff0c;例如总和、平均值、最大值、最小值等。它们通常与GROUP BY子句一起使用&#xff0c;以对数据分组后再计算聚合结果。 以下是SQL中常用的聚合函数及其详细讲解&#xff1a; 1. COUNT( )…

STM32编程遇到的问题随笔【一】

STM32编程遇到的问题随笔【一】 一、PB4引脚输出一直为高&#xff0c;无论怎么拉低都不起作用 原因PB4和PB3是复用引脚&#xff0c;用于JTAG调试&#xff0c;芯片是默认开启JTAG功能的&#xff0c;如果我们需要用到这两个引脚&#xff0c;必须降JTAG调试功能关闭&#xff0c;…

C语言和C++的不同

C语言和C都是非常重要的编程语言&#xff0c;它们有着紧密的联系&#xff0c;但也存在显著的差异。以下是对C语言和C的一些主要异同的分析&#xff0c;以及对常用语句的对比。 1. 基本概念与用途 C语言&#xff1a;C语言是一种过程式编程语言&#xff0c;它提供了对低级内存操…

Ubuntu问题 - 显示ubuntu服务器上可用磁盘空间 一条命令df -h

目的 想要放我的 数据集 到新的ubuntu服务器中, 不知道存储空间够不够 开始 使用以下命令直接查看 df -h

【RK3588 Linux 5.x 内核编程】-内核线程

内核线程 文章目录 内核线程1、进程与线程介绍2、线程管理3、内核线程管理函数3.1 创建内核线程3.2 启动内核线程3.3 停止内核线程4、内核线程示例实现4.1 内核线程函数定义4.2 创建和启动内核线程4.3 停止内核线程4.4 完整示例代码5、驱动验证线程是并发处理中使用的编程抽象。…

.NET9 - 新功能体验(一)

被微软形容为“迄今为止最高效、最现代、最安全、最智能、性能最高的.NET版本”——.NET 9已经发布有一周了&#xff0c;今天想和大家一起体验一下新功能。 此次.NET 9在性能、安全性和功能等方面进行了大量改进&#xff0c;包含了数千项的修改&#xff0c;今天主要和大家一起体…