Leetcode 726. Number of Atoms

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

1. Description

2. Solution

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

• Version 1

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] += chelif ch.isdigit():if formula[index - 1].isdigit():parts[-1] += chelse: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 = 1i = len(stack) - 1while stack[i] != '(':if isinstance(stack[i], int):stack[i] = stack[i] * multiplieri -= 1stack.pop(i)# Stat the number of atomsfor 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 + keyreturn result

Reference

1. https://leetcode.com/problems/number-of-atoms/