Leetcode 726. Number of Atoms

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Number of Atoms

2. Solution

解析:这道题还有优化的空间,这样写主要是逻辑清晰。1. 把元素(多个字母)、数字(多个数字字符)、左右括号拆分开;2. 计算元素的个数,如果元素后没有数字,则添加数字1作为元素个数;当碰到右括号时,查找其对应的左括号,并将其中的元素个数乘以括号后的数字,其后没数字,则默认乘以1;3. 统计元素个数,相同元素个数相加;4. 排序字典,按元素字母排序;5. 构造返回结果字符串。

  • Version 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution:
def countOfAtoms(self, formula):
stat = {}
stack = []
parts = []
# Split string by alpha, number, '(', ')'
for index, ch in enumerate(formula):
if ch.isupper():
parts.append(ch)
elif ch.islower():
parts[-1] += ch
elif ch.isdigit():
if formula[index - 1].isdigit():
parts[-1] += ch
else:
parts.append(ch)
else:
parts.append(ch)
# Calculate the number of atom and remove '(', ')'
stack = []
for index, part in enumerate(parts):
if part.isalpha():
if index + 1 == len(parts) or not parts[index + 1].isdigit():
stack.append(part)
stack.append(1)
else:
stack.append(part)
elif part.isdigit() and parts[index - 1] != ')':
stack.append(int(part))
elif part == '(':
stack.append(part)
elif part == ')':
if index + 1 < len(parts) and parts[index + 1].isdigit():
multiplier = int(parts[index + 1])
else:
multiplier = 1
i = len(stack) - 1
while stack[i] != '(':
if isinstance(stack[i], int):
stack[i] = stack[i] * multiplier
i -= 1
stack.pop(i)
# Stat the number of atoms
for i in range(0, len(stack), 2):
if stack[i] in stat:
stat[stack[i]] += stack[i + 1]
else:
stat[stack[i]] = stack[i + 1]
stat = sorted(stat.items(), key=lambda item: item[0])
result = ''
for key, value in stat:
if value > 1:
result = result + key + str(value)
else:
result = result + key
return result

Reference

  1. https://leetcode.com/problems/number-of-atoms/
如果有收获,可以请我喝杯咖啡!