【LeetCode】726、原子的数量

【LeetCode】726、原子的数量

一、递归: 嵌套类问题

1.1 递归: 嵌套类问题

遇到 ( 括号, 则递归计算子问题
遇到大写字母, 或遇到 ( 括号, 则清算历史, 并开始新的记录
记录由两部分组成: 大写字母开头的 或 子函数递归的结果

// go
func countOfAtoms(s string) string {where := 0 // 全局变量, 记录 括号内递归 的终止位置, 用于继续从此计算var f func(i int) map[string]int // 输入 s 的下标, 输出 哈希表, 计算括号内的 原子统计f = func(i int) map[string]int {m := map[string]int{}name := "" // 字母历史, 如 Mg4 的 Mgpre := map[string]int{} // 哈希表历史, 如 (SO3)2 的 SO3cnt := 0 // 次数, 如 Mg4 的 4, 如 (SO3)2 的 2for i < len(s) && s[i] != ')' {c := s[i]if (c >= 'A' && c <= 'Z') || c == '(' { // 需要清算历史记录, 并开始新的记录// 清算历史记录fill(m, name, pre, cnt)name = ""clear(pre)cnt = 0// 开始新的记录if c >= 'A' && c <= 'Z' { // 大写字母name += string(c) // 通过字母得到记录i++} else { // 左括号 (pre = f(i+1) // 通过递归得到记录i = where + 1 // 从递归结束的位置, 继续遍历}} else if c >= 'a' && c <= 'z' {name += string(c)i++} else { // 数字 c >= '0' && c <= '9'cnt = cnt * 10 + int(c - '0')i++}}fill(m, name, pre, cnt) // 最后一次, 比如 H2Mg3, 当遍历到整个字符串结尾时 需要触发 把 最后的 Mg3 放入结果where = i // 标记此递归的结束位置, 后续顶层函数继续从 where + 1 处遍历, 否则肯定死循环return m}m := f(0)return format(m)
}// name 重复 cnt 次, 或 pre 重复 cnt 次, 添加到 m 中
func fill(m map[string]int, name string, pre map[string]int, cnt int) {if cnt == 0 {cnt = 1} // 如 HMF 则 遍历到 M 时, 需清算 H, 但此时 cnt 为 0, 其实是因为省略了 H1 为 H, 所以需要当 cnt == 0 时把 cnt 置为 1if len(name) > 0 { // 是 name 的历史m[name]+=cnt} else { // 是 pre 的历史for atom, count := range pre {m[atom]+=count*cnt}}
}func format(m map[string]int) (ans string) {sli := slices.Collect(maps.Keys(m)) // 无需哈希表, 收集 keysslices.Sort(sli) // 排序 keys, 从而得到有序哈希表for _, atom := range sli {cnt := m[atom]ans += atomif cnt > 1 {ans += strconv.Itoa(cnt)}}return
}

参考左神: 嵌套类问题 递归思路

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts