LeetCode 726. 原子的数量

2026-09-21 HGNULB 约 8 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 困难未解决 5-10 字节阿里

题目描述

✅ 726. 原子的数量

题意分析

解析一个有效化学式，统计每一种原子的总数量，再按原子名称的字典序输出。原子名由一个大写字母和其后连续的小写字母组成；名称后面的完整数字表示数量，没有数字时默认为一。

括号内仍是一段完整化学式，可以继续嵌套；右括号后的数字乘到整个括号组的每一种原子上，省略时也为一。相同原子即使出现在不同位置或不同括号层级，最终都要合并计数，输出数量为一时省略数字。

题目保证公式有效，英文题面还明确保证输出计数能放入 32 位整数，因此当前整数计数实现符合数值范围。

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

核心思路

[!blue]

括号天然划分局部作用域。让 parseGroup 负责解析当前作用域，返回一张“原子名到出现数量”的表；整个字符串也是最外层作用域。共享下标 index 始终指向下一个尚未消费的字符，子调用读过的部分无需父调用重新扫描。

遇到原子时，先读取起始大写字母及后面连续的小写字母，形成完整名称；再连续读取其后的全部数字，得到数量。没有数字时返回默认值一，并保持下标指向下一段内容。将这个数量累加到当前表中，不能覆盖同名原子此前的贡献。

遇到左括号时，先越过它，递归解析内层。内层遇到右括号就返回，但故意不消费这个右括号；由调用方统一越过右括号，再读取后面的倍数。这样父调用既拿到了内层完整计数，也知道紧跟这组内容的倍数是什么，可以把每个内层计数乘上倍数后累加到本层。

嵌套的乘法由返回过程自然完成：最内层先处理自己的倍数，再作为完整结果交给外层乘上外层倍数。每一层只维护本层计数，不会把一个括号后的倍数误用到括号外的其他原子上。

顶层在字符串末尾结束，得到全部原子的总量。最后再按名称排序并拼接输出，避免让输入中的出现顺序或哈希表的遍历顺序决定结果。Java 每次入口重置公式和下标，Go 使用当前调用的局部下标，多次调用相互独立。

解题步骤

将共享解析下标置为零，调用一次 parseGroup 解析最外层。

当前字符是原子起点时，读取完整原子名与可选的多位数量，累加到本层表。

当前字符是左括号时，先进入内层递归；返回后由本层越过右括号，读取组倍数，再逐项合并内层结果。

当前作用域遇到右括号或字符串末尾时停止并返回计数表，右括号保留给调用方消费。

将最终原子名按字典序排列，逐个输出名称；只有数量大于一时才追加数字。

代码实现

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)$，递归栈、各层仍存活的计数表和名称总量都受公式长度约束，不需要展开倍数对应的实际原子序列。

关键点总结

[!green]

每层递归返回独立的计数表，括号后的倍数只作用于这张内层表。

子调用停在右括号前，父调用负责越过它并读取倍数，消费职责不能重复或遗漏。

原子名和数字都要完整读取，省略数量时默认一且不额外移动下标。

同名原子相加，最终名称排序与计数过程分开处理。

易错点总结

[!yellow]

把小写字母当成新的原子，或数量只读一位，都会把一个完整词元拆错。

子调用和父调用都跳过右括号，会漏掉组倍数或下一段；两边都不跳过则无法继续解析。

只给括号内最后一个原子乘倍数，遗漏了同一组中的其他原子。

合并同名原子时直接赋值，会覆盖此前在本层或其他子组中已经累计的数量。

直接遍历哈希表输出，不能保证原子名称按字典序排列。

输出数量一时也追加数字，违背题目指定的结果格式。

相似题目

题目	难度	关联与区别
394. 字符串解码	中等	两题都解析嵌套并应用倍数；本题倍数跟在原子或右括号之后，作用于原子计数；394的重复次数写在左括号之前，作用于括号内字符串。
736. Lisp 语法解析	困难	同样每层维护独立解析状态，本题是计数表，Lisp解析还需维护变量作用域。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/13814431

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！