【LeetCode】726、原子的数量

devtools/2024/12/28 1:55:12/

【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.ppmy.cn/devtools/145592.html

相关文章

SSM 架构下 Vue 电脑测评系统:为电脑性能评估赋能

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常适…

使用 C# 代码计算数学表达式

此程序展示了如何使用 C# 代码来计算数学表达式。该程序以以下代码开始。 此代码声明了一个Dictionary&#xff0c;稍后将使用它来保存变量。&#xff08;例如&#xff0c;如果用户想要 A 10、B 3 和 Pi 3.14159265。&#xff09; 然后它定义了一个Precedence枚举来表示运算…

原点安全再次入选信通院 2024 大数据“星河”案例

近日&#xff0c;中国信息通信研究院和中国通信标准化协会大数据技术标准推进委员会&#xff08;CCSA TC601&#xff09;共同组织开展的 2024 大数据“星河&#xff08;Galaxy&#xff09;”案例征集活动结果正式公布。由工银瑞信基金管理有限公司、北京原点数安科技有限公司联…

“信任构建”:网上购物商城的用户评价与信誉系统

2 相关技术 2.1 SSM框架介绍 本课题程序开发使用到的框架技术&#xff0c;英文名称缩写是SSM&#xff0c;在JavaWeb开发中使用的流行框架有SSH、SSM、SpringMVC等&#xff0c;作为一个课题程序采用SSH框架也可以&#xff0c;SSM框架也可以&#xff0c;SpringMVC也可以。SSH框架…

iOS AccentColor 和 Color Set

AccentColor 和 Color Set 都是 Xcode 中用于颜色管理的功能&#xff0c;它们适用于不同的开发场景和需求。以下是它们的区别和应用场景分析&#xff1a; 1. AccentColor&#xff08;强调色&#xff09; 1.1 概念&#xff1a; • AccentColor 是在 Xcode 12 中引入的&#xf…

编码转换(实例)

前四期 字符编码(四)-CSDN博客 实现二进制、八进制、十进制、十六进制互换转换&#xff1a; Java编码转换 import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);System.out.println("欢迎…

R 语言 | 绘图的文字格式(绘制上标、下标、斜体、文字标注等)

1. 上下标 # 注意y轴标签文字 library(ggplot2) ggplot(mtcars, aes(mpg, cyl))geom_point()ylab(label bquote(O[3]~(ug / m^3)))2. 希腊字母&#xff0c;如alpha ggplot(mtcars, aes(mpg, cyl))geom_point()ylab(label bquote(O[3]~(ug / m^3)))ggtitle(expression(alpha))…

ThinkPHP接入PayPal支付

ThinkPHP 5接入PayPal 支付&#xff0c;PayPal的流程是服务器请求Paypal的接口下单&#xff08;需要传订单id/支付成功的重定向地址/支付失败的重定向地址&#xff09;&#xff0c;接会返回一个支付地址&#xff0c;项目服务器把地址返给用户&#xff0c;用户打开链接登录Paypa…