LeetCode：726. Number of Atoms - Python

问题描述给定一个化学式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}。注意:所有原子的第一个字母为大写剩余字母都是小写。formula的长度在[1, 1000]之间。formula只包含字母、数字和圆括号并且题目中给定的是合法的化学式。问题分析很显然这是一个递归题目可以使用递归实现、栈实现还有大神用正则来解决的具体的大家可以去网上搜索。现在参考了cnkyzz大神的程序进行一下学习总结。个人偏好还是非递归较好感觉还是for循环和栈跑的快哈。其基本思路是1从右向左遍历 formula 字符串这样处理的好处是可以比较方便推出字符原子的系数 coeff。2遇到数字时则记录在变量cnt中其中i用于记录数字的位数原子的系数不仅仅是个位数的。3遇到符号)时则把当前的数字cnt压栈即把符号)右边的数字进栈。4遇到符号(时则把当前栈顶原子出栈即把相对应的)右边的数字出栈。5遇到大写字母时把当前的原子变量elem放入字典注意个数的计算要考虑之前是否已经存在。6遇到小写字母时保留到当前原子变量elem中。7最后字典排序按照要求输出。Python3实现注collections.defaultdict(int)表示创建一个类似dictionary对象里面任何的values都是int的实例而且就算是一个不存在的key, d[key] 也有一个默认值这个默认值是int类型且默认值为 0.import collections class Solution: def countOfAtoms(self, formula): dic, coeff, stack, elem, cnt, i collections.defaultdict(int), 1, [], , 0, 0 for c in formula[::-1]: if c.isdigit(): cnt int(c) * (10 ** i) # 获取当前数子 i 1 # 当前数字的位数 elif c ): # 当前数字入栈并更新当前原子的系数 num cnt if cnt ! 0 else 1 # # 没有数字默认是 1 stack.append(num) coeff * num i cnt 0 elif c (: # 出栈并更新当前系数相除哦 coeff // stack.pop() i cnt 0 elif c.isupper(): # 原子写入字典 elem c elem dic[elem] (cnt or 1) * coeff # 当前数字 * 当前的系数 之前已经存在的个数。 elem i cnt 0 elif c.islower(): # 拼接保留到 elem 中 elem c elem return .join(k str(v 1 and v or ) for k, v in sorted(dic.items())) if __name__ __main__: solu Solution() formula K4(ON(SO3)2)2 print(formula:, K4(ON(SO3)2)2) print(solu.countOfAtoms(formula))欢迎指正哦。