0726：原子的数量（★★）

Ian

2016-12-26 约 948 字预计阅读 2 分钟次阅读

力扣第 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 总是有效的化学式

分析

#1

典型的栈问题。数量可能很大，所以考虑栈中不保存字符，而是保存计数字典 Counter()。

先考虑没有括号的情况。遇到大写字母时，向后提取出原子的名字，再向后提取出数量，累加到 stack[-1] 中即可。

再考虑有括号的情况。遇到左括号就新加一个 Counter()，用来保存括号内的结果。遇到右括号时就弹出栈顶的 ct，然后向后提取出数字 cnt，将 ct 的每个原子数量乘以 cnt，累加到 stack[-1] 中即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


def countOfAtoms(self, formula: str) -> str:
	stack, i, n = [Counter()], 0, len(formula)
	while i < n:
		if formula[i].isupper():
			j = i
			i += 1
			while i < n and formula[i].islower():
				i += 1
			atom = formula[j:i]
			j = i
			while i < n and formula[i].isdigit():
				i += 1
			cnt = int(formula[j:i] or 1)
			stack[-1][atom] += cnt
		elif formula[i] == '(':
			stack.append(Counter())
			i += 1
		else:
			ct = stack.pop()
			i += 1
			j = i
			while i < n and formula[i].isdigit():
				i += 1
			cnt = int(formula[j:i] or 1)
			for k, v in ct.items():
				stack[-1][k] += v*cnt
	res, ct = '', stack.pop()
	for atom in sorted(ct):
		cnt = ct[atom]
		res += atom + str(cnt if cnt > 1 else '')
	return res

36 ms

#2

可以用正则来节省代码。每轮提取 “原子名字+数量” 或 “(” 或 “)+数量”，其它的流程一样。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def countOfAtoms(self, formula: str) -> str:
	stack, regex = [Counter()], r"([A-Z][a-z]*)(\d*)|(\()|(\))(\d*)"
	for atom, cnt, left, right, cnt2 in re.findall(regex, formula):
		if atom:
		  stack[-1][atom] += int(cnt or 1)
		elif left:
		  stack.append(Counter())
		elif right:
			ct = stack.pop()
			for k, v in ct.items():
			  stack[-1][k] += v * int(cnt2 or 1)

	res, ct = '', stack.pop()
	for atom in sorted(ct):
		cnt = ct[atom]
		res += atom + str(cnt if cnt > 1 else '')
	return res

28 ms

目录

0726：原子的数量（★★）

题目

分析

#1

#2

解答