南京建设人才网站,弹窗视频网站,包头seo优化,中国4a广告公司有哪些【LeetCode】726、原子的数量 文章目录 一、递归: 嵌套类问题1.1 递归: 嵌套类问题 二、多语言解法 一、递归: 嵌套类问题
1.1 递归: 嵌套类问题
遇到 ( 括号, 则递归计算子问题 遇到大写字母, 或遇到 ( 括号, 则清算历史, 并开始新的记录 记录由两部分组成: 大写字母开头的 …【LeetCode】726、原子的数量 文章目录 一、递归: 嵌套类问题1.1 递归: 嵌套类问题 二、多语言解法 一、递归: 嵌套类问题
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(i1) // 通过递归得到记录i where 1 // 从递归结束的位置, 继续遍历}} else if c a c z {name string(c)i} else { // 数字 c 0 c 9cnt 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
}参考左神: 嵌套类问题 递归思路
二、多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp// go 同上# python// rust// js// ts
