Hard

题目描述

给你一个字符串化学式 formula ，返回 每种原子的数量 。

原子总是以一个大写字母开始，然后跟随0个或任意个小写字母，表示原子的名字。

如果数量大于1，原子后会跟着数字表示原子的数量。如果数量等于1则不会跟数字。

  • 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。

两个化学式连在一起可以构成新的化学式。

  • 例如 "H2O2He3Mg4" 也是化学式。

由括号括起的化学式并佐以数字（可选择性添加）也是化学式。

  • 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。

返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于1），以此类推。

保证题目中所有测试用例的答案都在 32-bit 整数范围内。

示例 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. 栈 + 哈希表方法：使用栈来处理括号嵌套，每个栈元素是一个哈希表记录当前层级的原子计数

    • 遇到 ( 时，将新的空哈希表入栈
    • 遇到 ) 时，弹出栈顶哈希表，将其内容乘以后续倍数后合并到下一层
    • 解析原子名和数量，累加到当前栈顶的哈希表

  2. 递归方法：使用递归函数处理括号内容，每次递归返回一个哈希表

实现细节：

  • 解析原子名：大写字母开头，后跟0个或多个小写字母
  • 解析数字：连续的数字字符，需考虑没有数字的情况（默认为1）
  • 括号处理：遇到左括号时开始新层级，遇到右括号时处理倍数并合并到上层
  • 最终输出：按字典序排序，数量为1时不显示

推荐使用栈方法，思路清晰且易于实现。

代码实现

class Solution {
public:
    string countOfAtoms(string formula) {
        stack<unordered_map<string, int>> stk;
        stk.push({});
        
        int i = 0;
        while (i < formula.size()) {
            if (formula[i] == '(') {
                stk.push({});
                i++;
            } else if (formula[i] == ')') {
                auto top = stk.top();
                stk.pop();
                i++;
                int start = i;
                while (i < formula.size() && isdigit(formula[i])) {
                    i++;
                }
                int multiplier = (start == i) ? 1 : stoi(formula.substr(start, i - start));
                for (auto& [atom, count] : top) {
                    stk.top()[atom] += count * multiplier;
                }
            } else {
                int start = i++;
                while (i < formula.size() && islower(formula[i])) {
                    i++;
                }
                string atom = formula.substr(start, i - start);
                start = i;
                while (i < formula.size() && isdigit(formula[i])) {
                    i++;
                }
                int count = (start == i) ? 1 : stoi(formula.substr(start, i - start));
                stk.top()[atom] += count;
            }
        }
        
        map<string, int> counter(stk.top().begin(), stk.top().end());
        string result;
        for (auto& [atom, count] : counter) {
            result += atom;
            if (count > 1) {
                result += to_string(count);
            }
        }
        return result;
    }
};

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        stack = [{}]
        i = 0
        
        while i < len(formula):
            if formula[i] == '(':
                stack.append({})
                i += 1
            elif formula[i] == ')':
                top = stack.pop()
                i += 1
                start = i
                while i < len(formula) and formula[i].isdigit():
                    i += 1
                multiplier = 1 if start == i else int(formula[start:i])
                for atom, count in top.items():
                    stack[-1][atom] = stack[-1].get(atom, 0) + count * multiplier
            else:
                start = i
                i += 1
                while i < len(formula) and formula[i].islower():
                    i += 1
                atom = formula[start:i]
                start = i
                while i < len(formula) and formula[i].isdigit():
                    i += 1
                count = 1 if start == i else int(formula[start:i])
                stack[-1][atom] = stack[-1].get(atom, 0) + count
        
        counter = stack[0]
        result = []
        for atom in sorted(counter.keys()):
            result.append(atom)
            if counter[atom] > 1:
                result.append(str(counter[atom]))
        return ''.join(result)

public class Solution {
    public string CountOfAtoms(string formula) {
        var stack = new Stack<Dictionary<string, int>>();
        stack.Push(new Dictionary<string, int>());
        
        int i = 0;
        while (i < formula.Length) {
            if (formula[i] == '(') {
                stack.Push(new Dictionary<string, int>());
                i++;
            } else if (formula[i] == ')') {
                var top = stack.Pop();
                i++;
                int start = i;
                while (i < formula.Length && char.IsDigit(formula[i])) {
                    i++;
                }
                int multiplier = (start == i) ? 1 : int.Parse(formula.Substring(start, i - start));
                foreach (var kvp in top) {
                    if (stack.Peek().ContainsKey(kvp.Key)) {
                        stack.Peek()[kvp.Key] += kvp.Value * multiplier;
                    } else {
                        stack.Peek()[kvp.Key] = kvp.Value * multiplier;
                    }
                }
            } else {
                int start = i++;
                while (i < formula.Length && char.IsLower(formula[i])) {
                    i++;
                }
                string atom = formula.Substring(start, i - start);
                start = i;
                while (i < formula.Length && char.IsDigit(formula[i])) {
                    i++;
                }
                int count = (start == i) ? 1 : int.Parse(formula.Substring(start, i - start));
                if (stack.Peek().ContainsKey(atom)) {
                    stack.Peek()[atom] += count;
                } else {
                    stack.Peek()[atom] = count;
                }
            }
        }
        
        var counter = stack.Peek();
        var result = new StringBuilder();
        foreach (var atom in counter.Keys.OrderBy(x => x)) {
            result.Append(atom);
            if (counter[atom] > 1) {
                result.Append(counter[atom]);
            }
        }
        return result.ToString();
    }
}

var countOfAtoms = function(formula) {
    const stack = [{}];
    let i = 0;
    
    while (i < formula.length) {
        if (formula[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + k log k)
空间复杂度O(n + k)

其中 n 为字符串长度，k 为不同原子的数量。时间复杂度包括遍历字符串的 O(n) 和排序输出的 O(k log k)。空间复杂度主要用于栈和哈希表存储。

相关题目