LeetCode: 726. 原子的数量¶
1、题目描述¶
给定一个化学式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只包含字母、数字和圆括号,并且题目中给定的是合法的化学式。
2、解题思路¶
- 首先进行预处理
首先将它们分成不同的部分
"Mg(OH)2" => ['Mg', '(OH)2'] "((N42)24(OB40Li30CHe3O48LiNN26)33(C12Li48N30H13HBe31)21(BHN30Li26BCBe47N40)15(H5)16)14" => ['((N42)24(OB40Li30CHe3O48LiNN26)33(C12Li48N30H13HBe31)21(BHN30Li26BCBe47N40)15(H5)16)14'] '((N42)24(OB40Li30CHe3O48LiNN26)33(C12Li48N30H13HBe31)21(BHN30Li26BCBe47N40)15(H5)16)14' => ['(N42)24', '(OB40Li30CHe3O48LiNN26)33', '(C12Li48N30H13HBe31)21', '(BHN30Li26BCBe47N40)15', '(H5)16']
如上,将不同的部分进行拆分,然后针对括号中的进行递归处理
最后返回的结果为字典,按字典序排序后生成结果值
from string import ascii_lowercase, ascii_uppercase, digits from collections import defaultdict class Solution: def countOfAtoms(self, formula: str) -> str: if not formula: return "" lower = set(ascii_lowercase) upper = set(ascii_uppercase) nums = set(digits) def get_atom(form): pass pre_processing = [] length = len(form) pos = 0 temp = [] while pos < length: current = form[pos] if current in upper and not temp: temp.append(current) elif current in lower or current in nums: temp.append(current) elif current in upper and temp: pre_processing.append("".join(temp)) temp = [current] elif current == "(": if temp: pre_processing.append("".join(temp)) start = pos stack = ["("] pos += 1 while pos < length: if form[pos] == ")": stack.pop() if not stack: break elif form[pos] == "(": stack.append("(") pos += 1 temp = [form[start:pos+1]] pos += 1 if temp: pre_processing.append("".join(temp)) result = defaultdict(int) for s in pre_processing: if s[0] == "(": count = 1 if s[-1] in nums: count = int(s[s.rindex(")") + 1:]) for atom, n in get_atom(s[1:s.rindex(")")]).items(): result[atom] += n * count else: if s[-1] in nums: for index, char in enumerate(s): if char in nums: result[s[:index]] += int(s[index:]) break else: result[s] += 1 return result res = get_atom(formula) ans = [] for atom_name in sorted(res.keys()): if res[atom_name] == 1: ans.append(atom_name) elif res[atom_name] > 1: ans.append(atom_name + str(res[atom_name])) return "".join(ans)