LeetCode 726. Number of Atoms 题解Go 实现栈 哈希表解析化学式【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 726 题「原子的数量Number of Atoms」以本仓库LeetCode-Go中 0726.Number-of-Atoms 的题解为核心完整讲解题目规则、栈与哈希表的解题思路、可运行的 Go 源码逐段剖析以及基于仓库测试用例的验证方法。读完本文你将掌握如何用「token 化 嵌套层级计数」的方式解析任意含括号与数字的化学式并理解排序输出的格式化细节。题目描述给定一个化学式formula以字符串形式给出返回每个原子的数量。原子元素总是以一个大写字母开头后跟零个或多个小写字母表示元素名称如果该元素数量大于 1原子后可能跟着一位或多位数字表示数量如果数量为 1则不会跟数字。例如H2O与H2O2是合法的而H1O2不合法两个化学式拼接在一起得到新的化学式例如H2O2He3Mg4也是合法化学式括号内的化学式外加一个可选的数字也是合法化学式例如(H2O2)与(H2O2)3。输出要求按字典序sorted order输出所有元素先输出元素名称再输出数量仅当数量大于 1 时输出数量以此类推。示例 1Input: formula H2O Output: H2O Explanation: The count of elements are {H: 2, O: 1}.示例 2Input: formula Mg(OH)2 Output: H2MgO2 Explanation: The count of elements are {H: 2, Mg: 1, O: 2}.示例 3Input: formula K4(ON(SO3)2)2 Output: K4N2O14S4 Explanation: The count of elements are {K: 4, N: 2, O: 14, S: 4}.约束说明来自原题 Note所有原子名称除首字符为大写外其余均为小写字母formula的长度范围为[1, 1000]formula只包含字母、数字和圆括号且保证是符合上述定义的合法化学式。题目大意给定一个化学式字符串统计其中每种原子的个数。输出格式为按字典序依次排列每种原子原子名后面跟随其数量数量大于 1 时形如K4N2O14S4。一个容易忽略的细节是化学元素并非都是单字母例如镁元素是Mg因此在解析时必须处理字母的大小写将「大写字母 若干小写字母」作为一个完整的原子名称读取而不能简单地按单个字符处理。解题思路原文档给出的解题思路是利用栈处理每个化学元素用 map 记录每个化学元素的个数最终排序以后输出即可注意化学元素有些并不是单一字母比如镁元素是Mg所以需要考虑字母的大小写问题。仓库中的 核心实现 正是沿着这条思路落地具体分为两大阶段第一阶段字符串 token 化词法分析从左到右扫描原始字符串把化学式切分成四类 token并压入栈stack []string左括号(与右括号)直接作为单个 token原子名遇到大写字母时连续读取其后的小写字母得到一个完整的原子名 token如Mg、O数字连续读取数字字符得到一个完整的多位数字 token如200。第二阶段按括号层级计数语义计算用一个深度指针deep与一个按层级划分的计数数组cnt [100]map[string]int模拟嵌套括号遇到原子名 token读取紧随其后的数字 token 作为数量没有数字则数量为 1累加到cnt[deep]遇到(deep进入更深一层遇到)读取紧随其后的数字 token 作为括号重复次数没有则视为 1将当前层级cnt[deep]中的每个原子数量乘以该次数并入父层级cnt[deep-1]随后清空当前层级、deep--。扫描结束后cnt[0]即为全局原子计数表将其转换为可排序的结构体切片按原子名称字典序排序后拼接输出。关于层级深度的边界说明cnt被固定声明为长度 100 的 map 切片cnt : make([]map[string]int, 100)即实现假定括号嵌套深度不会超过 100 层。题目约束formula长度最大为 1000实际嵌套深度远小于该上限因此这一静态分配在本题约束下是安全的。这也是从源码中可以观察到的实现选择。源码实现详解仓库中的核心函数为countOfAtoms(s string) string下面逐段解读。1. 自定义原子类型与排序封装type atom struct { name string cnt int } type atoms []atom func (this atoms) Len() int { return len(this) } func (this atoms) Less(i, j int) bool { return strings.Compare(this[i].name, this[j].name) 0 } func (this atoms) Swap(i, j int) { this[i], this[j] this[j], this[i] } func (this atoms) String() string { s : for _, a : range this { s a.name if a.cnt 1 { s strconv.Itoa(a.cnt) } } return s }atoms类型实现了sort.Interface的三个方法Len/Less/Swap其中Less基于strings.Compare按名称字典序比较从而可以直接调用sort.Sort(as)完成排序。String()方法负责输出格式化原子名后仅当数量cnt 1时追加数字strconv.Itoa这与题目「数量为 1 时不输出数字」的规则完全对应。2. 第一阶段token 化func countOfAtoms(s string) string { n : len(s) if n 0 { return } stack : make([]string, 0) for i : 0; i n; i { c : s[i] if c ( || c ) { stack append(stack, string(c)) } else if isUpperLetter(c) { j : i 1 for ; j n; j { if !isLowerLetter(s[j]) { break } } stack append(stack, s[i:j]) i j - 1 } else if isDigital(c) { j : i 1 for ; j n; j { if !isDigital(s[j]) { break } } stack append(stack, s[i:j]) i j - 1 } } // ... }这段代码的关键点空串直接返回空字符串对应测试用例countOfAtoms() 原子名的识别依赖isUpperLetterisLowerLetter的配合只有「大写字母开头的连续小写字母串」才是一个完整原子名这正确处理了Mg、He等多字母元素数字采用「贪婪连续读取」的方式保证多位数字如H200P中的200作为一个完整 token 入栈借助i j - 1跳过已消费的字符外层循环继续扫描后续内容。3. 第二阶段层级计数与括号展开cnt, deep : make([]map[string]int, 100), 0 for i : 0; i 100; i { cnt[i] make(map[string]int) } for i : 0; i len(stack); i { t : stack[i] if isUpperLetter(t[0]) { num : 1 if i1 len(stack) isDigital(stack[i1][0]) { num, _ strconv.Atoi(stack[i1]) i } cnt[deep][t] num } else if t ( { deep } else if t ) { num : 1 if i1 len(stack) isDigital(stack[i1][0]) { num, _ strconv.Atoi(stack[i1]) i } for k, v : range cnt[deep] { cnt[deep-1][k] v * num } cnt[deep] make(map[string]int) deep-- } }这段代码是整个算法的核心每个括号层级对应一个独立的map[string]intdeep表示当前所在层级原子出现时先探测下一个 token 是否为数字isDigital(stack[i1][0])是则解析为数量并跳过该 tokeni否则数量默认为 1遇到)时将当前层级所有原子的计数乘以括号后的数字默认 1叠加到父层级的 map 中然后重置当前层级 map 并回退deep。这等价于把嵌套括号从内向外逐层「展开」最终所有计数都汇总到cnt[0]即最外层无括号包裹的全局统计。4. 排序与输出as : atoms{} for k, v : range cnt[0] { as append(as, atom{name: k, cnt: v}) } sort.Sort(as) return as.String()将cnt[0]中的键值对转换为atoms切片sort.Sort(as)按名称字典序排序最后通过String()方法完成「名称 数量1 时」的格式化拼接。5. 字符类别辅助函数func isDigital(v byte) bool { if v 0 v 9 { return true } return false } func isUpperLetter(v byte) bool { if v A v Z { return true } return false } func isLowerLetter(v byte) bool { if v a v z { return true } return false }三个辅助函数分别用于判断数字字符、大写字母与小写字母不依赖任何外部库逻辑清晰且性能开销极小常数级比较。测试用例验证仓库为本题提供了完整的单元测试 726. Number of Atoms_test.go覆盖以下用例输入formula期望输出覆盖点空串边界H200PH200P多位数字、数量为 1 不输出数字H2OH2O基础用例Mg(OH)2H2MgO2多字母元素 括号倍数K4(ON(SO3)2)2K4N2O14S4多层嵌套括号 字典序输出其中K4(ON(SO3)2)2是典型的嵌套用例SO3在两层括号内数量被2内层括号与2外层括号依次放大最终S为1×2×2 4O为3×2×2 12再加上ON中直接的1×2 2合计O 14与期望输出K4N2O14S4完全一致很好地验证了「从内向外逐层展开」的计数逻辑。测试函数Test_Problem726对每个用例调用countOfAtoms并与期望结果比对不匹配时通过t.Fatalf立即失败。该测试遵循仓库统一的表驱动风格可直接运行# 只运行本题测试需要 Go 工具链 go test -v -run Test_Problem726 ./leetcode/0726.Number-of-Atoms/ # 或按仓库 gotest.sh 的方式运行全部 leetcode 包测试并输出覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...后者正是仓库根目录 gotest.sh 中使用的命令它利用 Go 1.10 的多包-coverprofile能力一次性产出单个合法的覆盖率文件。仓库模块基于go 1.19见 go.mod上述命令在本地安装对应版本 Go 后即可执行。复杂度分析时间复杂度第一阶段 token 化每个字符只会被扫描一次为 O(n)n 为字符串长度第二阶段遍历 token 栈同样为 O(n)其中)展开时需要遍历当前层级的 map整体仍为 O(n) 量级最后的排序复杂度为 O(k log k)其中 k 为不同原子的种类数本题原子种类有限k 远小于 n。总体时间复杂度约为 O(n k log k)。空间复杂度token 栈与按层级划分的计数 map 均为 O(n) 量级其中层级 map 的数量是固定常数100 层。小结本题是「栈 哈希表」处理嵌套结构的经典应用先用一次扫描完成词法分析识别原子名、数字、括号三类 token再用层级化的 map 模拟括号的嵌套展开最后排序输出。仓库实现还额外处理了两个易错点多字母原子名的正确切分大小写判断与数量为 1 时省略数字的输出格式。对于面试或竞赛中类似的「解析嵌套表达式」问题如解码字符串、计算带括号的表达式这一「token 化 层级计数」的两段式思路同样具有直接的迁移价值。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 726. Number of Atoms 题解：Go 实现栈 + 哈希表解析化学式
LeetCode 726. Number of Atoms 题解Go 实现栈 哈希表解析化学式【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 726 题「原子的数量Number of Atoms」以本仓库LeetCode-Go中 0726.Number-of-Atoms 的题解为核心完整讲解题目规则、栈与哈希表的解题思路、可运行的 Go 源码逐段剖析以及基于仓库测试用例的验证方法。读完本文你将掌握如何用「token 化 嵌套层级计数」的方式解析任意含括号与数字的化学式并理解排序输出的格式化细节。题目描述给定一个化学式formula以字符串形式给出返回每个原子的数量。原子元素总是以一个大写字母开头后跟零个或多个小写字母表示元素名称如果该元素数量大于 1原子后可能跟着一位或多位数字表示数量如果数量为 1则不会跟数字。例如H2O与H2O2是合法的而H1O2不合法两个化学式拼接在一起得到新的化学式例如H2O2He3Mg4也是合法化学式括号内的化学式外加一个可选的数字也是合法化学式例如(H2O2)与(H2O2)3。输出要求按字典序sorted order输出所有元素先输出元素名称再输出数量仅当数量大于 1 时输出数量以此类推。示例 1Input: formula H2O Output: H2O Explanation: The count of elements are {H: 2, O: 1}.示例 2Input: formula Mg(OH)2 Output: H2MgO2 Explanation: The count of elements are {H: 2, Mg: 1, O: 2}.示例 3Input: formula K4(ON(SO3)2)2 Output: K4N2O14S4 Explanation: The count of elements are {K: 4, N: 2, O: 14, S: 4}.约束说明来自原题 Note所有原子名称除首字符为大写外其余均为小写字母formula的长度范围为[1, 1000]formula只包含字母、数字和圆括号且保证是符合上述定义的合法化学式。题目大意给定一个化学式字符串统计其中每种原子的个数。输出格式为按字典序依次排列每种原子原子名后面跟随其数量数量大于 1 时形如K4N2O14S4。一个容易忽略的细节是化学元素并非都是单字母例如镁元素是Mg因此在解析时必须处理字母的大小写将「大写字母 若干小写字母」作为一个完整的原子名称读取而不能简单地按单个字符处理。解题思路原文档给出的解题思路是利用栈处理每个化学元素用 map 记录每个化学元素的个数最终排序以后输出即可注意化学元素有些并不是单一字母比如镁元素是Mg所以需要考虑字母的大小写问题。仓库中的 核心实现 正是沿着这条思路落地具体分为两大阶段第一阶段字符串 token 化词法分析从左到右扫描原始字符串把化学式切分成四类 token并压入栈stack []string左括号(与右括号)直接作为单个 token原子名遇到大写字母时连续读取其后的小写字母得到一个完整的原子名 token如Mg、O数字连续读取数字字符得到一个完整的多位数字 token如200。第二阶段按括号层级计数语义计算用一个深度指针deep与一个按层级划分的计数数组cnt [100]map[string]int模拟嵌套括号遇到原子名 token读取紧随其后的数字 token 作为数量没有数字则数量为 1累加到cnt[deep]遇到(deep进入更深一层遇到)读取紧随其后的数字 token 作为括号重复次数没有则视为 1将当前层级cnt[deep]中的每个原子数量乘以该次数并入父层级cnt[deep-1]随后清空当前层级、deep--。扫描结束后cnt[0]即为全局原子计数表将其转换为可排序的结构体切片按原子名称字典序排序后拼接输出。关于层级深度的边界说明cnt被固定声明为长度 100 的 map 切片cnt : make([]map[string]int, 100)即实现假定括号嵌套深度不会超过 100 层。题目约束formula长度最大为 1000实际嵌套深度远小于该上限因此这一静态分配在本题约束下是安全的。这也是从源码中可以观察到的实现选择。源码实现详解仓库中的核心函数为countOfAtoms(s string) string下面逐段解读。1. 自定义原子类型与排序封装type atom struct { name string cnt int } type atoms []atom func (this atoms) Len() int { return len(this) } func (this atoms) Less(i, j int) bool { return strings.Compare(this[i].name, this[j].name) 0 } func (this atoms) Swap(i, j int) { this[i], this[j] this[j], this[i] } func (this atoms) String() string { s : for _, a : range this { s a.name if a.cnt 1 { s strconv.Itoa(a.cnt) } } return s }atoms类型实现了sort.Interface的三个方法Len/Less/Swap其中Less基于strings.Compare按名称字典序比较从而可以直接调用sort.Sort(as)完成排序。String()方法负责输出格式化原子名后仅当数量cnt 1时追加数字strconv.Itoa这与题目「数量为 1 时不输出数字」的规则完全对应。2. 第一阶段token 化func countOfAtoms(s string) string { n : len(s) if n 0 { return } stack : make([]string, 0) for i : 0; i n; i { c : s[i] if c ( || c ) { stack append(stack, string(c)) } else if isUpperLetter(c) { j : i 1 for ; j n; j { if !isLowerLetter(s[j]) { break } } stack append(stack, s[i:j]) i j - 1 } else if isDigital(c) { j : i 1 for ; j n; j { if !isDigital(s[j]) { break } } stack append(stack, s[i:j]) i j - 1 } } // ... }这段代码的关键点空串直接返回空字符串对应测试用例countOfAtoms() 原子名的识别依赖isUpperLetterisLowerLetter的配合只有「大写字母开头的连续小写字母串」才是一个完整原子名这正确处理了Mg、He等多字母元素数字采用「贪婪连续读取」的方式保证多位数字如H200P中的200作为一个完整 token 入栈借助i j - 1跳过已消费的字符外层循环继续扫描后续内容。3. 第二阶段层级计数与括号展开cnt, deep : make([]map[string]int, 100), 0 for i : 0; i 100; i { cnt[i] make(map[string]int) } for i : 0; i len(stack); i { t : stack[i] if isUpperLetter(t[0]) { num : 1 if i1 len(stack) isDigital(stack[i1][0]) { num, _ strconv.Atoi(stack[i1]) i } cnt[deep][t] num } else if t ( { deep } else if t ) { num : 1 if i1 len(stack) isDigital(stack[i1][0]) { num, _ strconv.Atoi(stack[i1]) i } for k, v : range cnt[deep] { cnt[deep-1][k] v * num } cnt[deep] make(map[string]int) deep-- } }这段代码是整个算法的核心每个括号层级对应一个独立的map[string]intdeep表示当前所在层级原子出现时先探测下一个 token 是否为数字isDigital(stack[i1][0])是则解析为数量并跳过该 tokeni否则数量默认为 1遇到)时将当前层级所有原子的计数乘以括号后的数字默认 1叠加到父层级的 map 中然后重置当前层级 map 并回退deep。这等价于把嵌套括号从内向外逐层「展开」最终所有计数都汇总到cnt[0]即最外层无括号包裹的全局统计。4. 排序与输出as : atoms{} for k, v : range cnt[0] { as append(as, atom{name: k, cnt: v}) } sort.Sort(as) return as.String()将cnt[0]中的键值对转换为atoms切片sort.Sort(as)按名称字典序排序最后通过String()方法完成「名称 数量1 时」的格式化拼接。5. 字符类别辅助函数func isDigital(v byte) bool { if v 0 v 9 { return true } return false } func isUpperLetter(v byte) bool { if v A v Z { return true } return false } func isLowerLetter(v byte) bool { if v a v z { return true } return false }三个辅助函数分别用于判断数字字符、大写字母与小写字母不依赖任何外部库逻辑清晰且性能开销极小常数级比较。测试用例验证仓库为本题提供了完整的单元测试 726. Number of Atoms_test.go覆盖以下用例输入formula期望输出覆盖点空串边界H200PH200P多位数字、数量为 1 不输出数字H2OH2O基础用例Mg(OH)2H2MgO2多字母元素 括号倍数K4(ON(SO3)2)2K4N2O14S4多层嵌套括号 字典序输出其中K4(ON(SO3)2)2是典型的嵌套用例SO3在两层括号内数量被2内层括号与2外层括号依次放大最终S为1×2×2 4O为3×2×2 12再加上ON中直接的1×2 2合计O 14与期望输出K4N2O14S4完全一致很好地验证了「从内向外逐层展开」的计数逻辑。测试函数Test_Problem726对每个用例调用countOfAtoms并与期望结果比对不匹配时通过t.Fatalf立即失败。该测试遵循仓库统一的表驱动风格可直接运行# 只运行本题测试需要 Go 工具链 go test -v -run Test_Problem726 ./leetcode/0726.Number-of-Atoms/ # 或按仓库 gotest.sh 的方式运行全部 leetcode 包测试并输出覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...后者正是仓库根目录 gotest.sh 中使用的命令它利用 Go 1.10 的多包-coverprofile能力一次性产出单个合法的覆盖率文件。仓库模块基于go 1.19见 go.mod上述命令在本地安装对应版本 Go 后即可执行。复杂度分析时间复杂度第一阶段 token 化每个字符只会被扫描一次为 O(n)n 为字符串长度第二阶段遍历 token 栈同样为 O(n)其中)展开时需要遍历当前层级的 map整体仍为 O(n) 量级最后的排序复杂度为 O(k log k)其中 k 为不同原子的种类数本题原子种类有限k 远小于 n。总体时间复杂度约为 O(n k log k)。空间复杂度token 栈与按层级划分的计数 map 均为 O(n) 量级其中层级 map 的数量是固定常数100 层。小结本题是「栈 哈希表」处理嵌套结构的经典应用先用一次扫描完成词法分析识别原子名、数字、括号三类 token再用层级化的 map 模拟括号的嵌套展开最后排序输出。仓库实现还额外处理了两个易错点多字母原子名的正确切分大小写判断与数量为 1 时省略数字的输出格式。对于面试或竞赛中类似的「解析嵌套表达式」问题如解码字符串、计算带括号的表达式这一「token 化 层级计数」的两段式思路同样具有直接的迁移价值。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考