LeetCode 726. 原子的数量

约 8 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节跳动 阿里巴巴
标签
字符串 哈希表 排序 栈
目录

题目描述

✅ 726. 原子的数量

题意分析

输入是一个合法的化学式字符串，输出要求把每种原子出现的总数统计出来，按原子名的字典序拼成一个字符串，数量为 1 时不写数字。这不是一个计算题，而是一个解析题：难点全在读懂输入的结构，而不在算什么。

输入的结构由三条规则拼出来：原子名是一个大写字母后跟零到多个小写字母（Mg 是一个原子而不是 M 加 g）；原子名后面可以紧跟一个多位十进制数表示个数，省略时为 1；括号可以任意嵌套，右括号后同样可以紧跟一个多位数，它对括号内的每一种原子都生效。

括号可以嵌套这一点是最强的算法信号：结构是递归的，而不是线性的，K4(ON(SO3)2)3 里的 SO3 要先乘 2 再随外层一起乘 3。凡是"内层结果需要被外层整体加工、且嵌套深度不定"的输入，就必须准备一个能保存"未完成的外层上下文"的容器，或者干脆写递归。

公式长度上限只有 1000，倍数不超过 1000，所以完全不必担心大数或性能，代码正确性和边界处理才是评分点。要留意的边界包括：数字缺省（H2O 里的 O）、多位数（Be32 要读成 32 而不是 3 和 2）、右括号紧跟另一个右括号（倍数为 1）、以及输出时数量恰好为 1 必须省略数字。

解法：递归下降解析括号作用域

核心思路

化学式由原子、数字和可嵌套括号组成，天然具有递归结构。与其展开字符串，不如让一次递归负责一个括号作用域，返回该作用域的“原子名 → 数量”统计表。

定义 parseGroup()：从当前下标开始扫描，直到遇到右括号或字符串结尾，并维护不变量：

函数返回时，统计表恰好包含当前作用域内已经完整解析的所有原子；下标停在当前作用域的右括号或字符串末尾。

遇到大写字母就读取完整原子名和紧随的多位数量，数量缺省为 1；遇到左括号就递归解析内层，递归返回后消费右括号及其倍数，再把内层每个计数乘倍数累加到当前表。

正确性可按括号嵌套深度归纳：没有括号时，每个原子及数量被准确累加；假设更深层作用域能正确返回统计表，那么当前层对它整体乘以右括号后的倍数并累加，也与化学式语义一致。最终最外层返回的表就是全式计数。

解题步骤

  • 用全局或引用下标从左到右扫描，避免重复切分未处理后缀。
  • 当前字符为大写字母：继续读取后续小写字母得到完整原子名，再读取多位数量，缺省为 1。
  • 当前字符为 (：跳过左括号，递归解析内层；返回后跳过 )，读取倍数并合并内层统计。
  • 当前字符为 ) 或已到末尾：结束当前递归并返回统计表。
  • 最外层解析结束后按原子名字典序输出；数量为 1 时省略数字。

以 K4(ON(SO3)2)3 为例：内层 SO3 得到 {S:1,O:3}，乘 2 后并入 ON 得 {O:7,N:1,S:2}；外层再乘 3，并与 K4 合并为 {K:4,N:3,O:21,S:6}，排序输出 K4N3O21S6。

代码实现

import java.util.*;

class Solution {
    private String formula;
    private int index;

    public String countOfAtoms(String formula) {
        this.formula = formula;
        this.index = 0;
        Map<String, Integer> counts = parseGroup();
        Map<String, Integer> sorted = new TreeMap<>(counts);

        StringBuilder ans = new StringBuilder();
        for (Map.Entry<String, Integer> entry : sorted.entrySet()) {
            ans.append(entry.getKey());
            if (entry.getValue() > 1) {
                ans.append(entry.getValue());
            }
        }
        return ans.toString();
    }

    private Map<String, Integer> parseGroup() {
        Map<String, Integer> counts = new HashMap<>();
        while (index < formula.length() && formula.charAt(index) != ')') {
            if (formula.charAt(index) == '(') {
                index++;
                Map<String, Integer> inner = parseGroup();
                index++;
                int multiplier = parseNumber();
                for (Map.Entry<String, Integer> entry : inner.entrySet()) {
                    counts.put(
                            entry.getKey(),
                            counts.getOrDefault(entry.getKey(), 0)
                                    + entry.getValue() * multiplier
                    );
                }
            } else {
                String atom = parseAtom();
                int count = parseNumber();
                counts.put(atom, counts.getOrDefault(atom, 0) + count);
            }
        }
        return counts;
    }

    private String parseAtom() {
        int start = index++;
        while (index < formula.length()
                && Character.isLowerCase(formula.charAt(index))) {
            index++;
        }
        return formula.substring(start, index);
    }

    private int parseNumber() {
        int start = index;
        int value = 0;
        while (index < formula.length()
                && Character.isDigit(formula.charAt(index))) {
            value = value * 10 + formula.charAt(index++) - '0';
        }
        return index == start ? 1 : value;
    }
}

import (
    "sort"
    "strconv"
    "strings"
)

func countOfAtoms(formula string) string {
    index := 0
    counts := parseGroup(formula, &index)

    atoms := make([]string, 0, len(counts))
    for atom := range counts {
        atoms = append(atoms, atom)
    }
    sort.Strings(atoms)

    var ans strings.Builder
    for _, atom := range atoms {
        ans.WriteString(atom)
        if counts[atom] > 1 {
            ans.WriteString(strconv.Itoa(counts[atom]))
        }
    }
    return ans.String()
}

func parseGroup(formula string, index *int) map[string]int {
    counts := make(map[string]int)
    for *index < len(formula) && formula[*index] != ')' {
        if formula[*index] == '(' {
            *index = *index + 1
            inner := parseGroup(formula, index)
            *index = *index + 1
            multiplier := parseNumber(formula, index)
            for atom, count := range inner {
                counts[atom] += count * multiplier
            }
        } else {
            atom := parseAtom(formula, index)
            counts[atom] += parseNumber(formula, index)
        }
    }
    return counts
}

func parseAtom(formula string, index *int) string {
    start := *index
    *index = *index + 1
    for *index < len(formula) &&
        formula[*index] >= 'a' && formula[*index] <= 'z' {
        *index = *index + 1
    }
    return formula[start:*index]
}

func parseNumber(formula string, index *int) int {
    start, value := *index, 0
    for *index < len(formula) &&
        formula[*index] >= '0' && formula[*index] <= '9' {
        value = value*10 + int(formula[*index]-'0')
        *index = *index + 1
    }
    if *index == start {
        return 1
    }
    return value
}

复杂度分析

设公式长度为 $n$、最大嵌套深度为 $d$、不同原子数为 $m$。

  • 时间复杂度：解析字符为 $O(n)$；计数表条目可能逐层向外合并，合并上界为 $O(nd)$，最坏即 $O(n^2)$；最终排序为 $O(m\log m)$。
  • 空间复杂度：$O(n)$。递归深度、各层统计表中的总条目数和输出规模都受公式长度限制。

关键点总结

  • 递归函数的返回值是“当前作用域的统计结果”，下标停在右括号前。
  • 原子名与数字都是变长词法单元，必须一次完整读取；数字缺省值为 1。
  • 右括号后的倍数作用于整个内层统计表，合并时必须累加而非覆盖。
  • 最终排序只决定输出顺序，不参与解析过程。

易错点总结

  • 把 Mg 拆成 M 和 g：原子名必须读取所有连续小写字母。
  • 数字只读取一位：Be32 会被错读为 3。
  • 递归返回后忘记跳过右括号：下一轮仍停在 )，下标无法推进。
  • 倍数只乘最近一个原子：它应作用于括号内整张统计表。
  • 合并时直接覆盖同名原子：外层已有计数会丢失。
  • 直接遍历哈希表输出：顺序不保证满足字典序。

相似题目

题目 难度 考察点
20. 有效的括号 简单 只用栈判嵌套是否合法，不需要在栈里携带任何计算结果
394. 字符串解码 中等 栈里存的是待拼接的字符串前缀和倍数，展开的是字符不是计数
224. 基本计算器 困难 括号影响的是正负号，可用一个符号栈代替整张表
772. 基本计算器 III 困难 括号内还有运算符优先级，需要在作用域上再叠一层求值逻辑
1096. 花括号展开 II 困难 作用域内维护的是字符串集合，合并时做并集与笛卡尔积
736. Lisp 语法解析 困难 括号绑定的是变量作用域，需要沿栈回溯查找变量的最近定义