当前位置: 首页 > news >正文

【LeetCode】726、原子的数量

【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(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
}

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

二、多语言解法

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
http://www.lryc.cn/news/509165.html

相关文章:

  • VMware虚拟机三种网络工作模式
  • 14-zookeeper环境搭建
  • [搜广推]王树森推荐系统笔记——矩阵补充最近邻查找
  • Unity3D * 粒子特效 * Particle System
  • 【基础篇】1. JasperSoft Studio编辑器与报表属性介绍
  • 数据结构:算法篇:快速排序;直接插入排序
  • WebAPI编程(第一天,第二天)
  • 查看MySQL存储引擎方法,表操作
  • 【Python教程】Python3基础篇之Number(数字)
  • 基于openEuler22.09部署OpenStack Yoga云平台(一)
  • I.MX6U 启动方式详解
  • 施耐德变频器ATV320系列技术优势:创新与安全并重
  • 系统思考—全局思维
  • Windows如何切换用户访问局域网共享文件夹,如何切换网上邻居的账户
  • 如何在谷歌浏览器中启用语音搜索
  • HarmonyOS NEXT 技术实践-基于基础视觉服务实现骨骼点识别
  • Debian系统宝塔面板安装LiteSpeed Memcached(LSMCD)
  • tcp 的三次握手与四次挥手
  • QT--信号与槽机制
  • vue3项目history路由模式部署上线405、刷新404问题(包括部分页面刷新404问题)
  • 电阻容差是啥意思
  • Rust: offset祼指针操作
  • SD本地部署和云端部署的区别以及优劣
  • 4、数据结构与算法解析(C语言版)--栈
  • c# 后台任务自动执行
  • 被裁20240927 --- 嵌入式硬件开发 前篇
  • 重温设计模式--观察者模式
  • vulnhub靶场——Log4j2
  • Vue3中使用resolve进行路径别名设置
  • Linux 添加磁盘