2022-08-30：给你一个字符串化学式 formula ，返回 每种原子的数量 。 原子总是以一个大写字

2022-08-30：给你一个字符串化学式 formula ，返回 每种原子的数量 。 原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。 两个化学式连在一起可以构成新的化学式。 例如 "H2O2He3Mg4" 也是化学式。 由括号括起的化学式并佐以数字（可选择性添加）也是化学式。 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。 返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1）， 然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。 示例 1： 输入：formula = "H2O" 输出："H2O" 解释：原子的数量是 {'H': 2, 'O': 1}。 示例 2： 输入：formula = "Mg(OH)2" 输出："H2MgO2" 解释：原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。 示例 3： 输入：formula = "K4(ON(SO3)2)2" 输出："K4N2O14S4" 解释：原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

答案2022-08-30：

递归。遇到左括号，进入递归；遇到右括号，退出递归。要用到TreeMap，rust里是std::collections::BTreeMap。

代码用rust编写。代码如下：

use std::collections::BTreeMap;
fn main() {
    let s = "K4(ON(SO3)2)2";
    let ans = count_of_atoms(s);
    println!("ans = {}", ans);
}
fn count_of_atoms(str: &str) -> String {
    let s = str.as_bytes();
    let info = process(s, 0);
    let mut builder: String = String::new();
    for (key, _) in info.cnt_map.iter() {
        builder.push_str(key);
        let cnt = *info.cnt_map.get(key).unwrap();
        if cnt > 1 {
            builder.push_str(&format!("{}", cnt));
        }
    }
    return builder;
}

pub struct Info {
    cnt_map: BTreeMap<String, i32>,
    end: i32,
}

impl Info {
    pub fn new(c: BTreeMap<String, i32>, e: i32) -> Self {
        Self { cnt_map: c, end: e }
    }
}

fn process(s: &[u8], i: i32) -> Info {
    let mut cnt_map: BTreeMap<String, i32> = BTreeMap::new();
    let mut cnt = 0;
    let mut builder: String = String::new();
    let mut info: Info = Info::new(BTreeMap::new(), 0);
    let mut i = i;
    while i < s.len() as i32 && s[i as usize] != ')' as u8 {
        if s[i as usize] >= 'A' as u8 && s[i as usize] <= 'Z' as u8 || s[i as usize] == '(' as u8 {
            if builder.len() != 0 || info.end != 0 {
                cnt = if cnt == 0 { 1 } else { cnt };
                if builder.len() != 0 {
                    let key = builder.clone();
                    cnt_map.insert(
                        key.clone(),
                        if cnt_map.contains_key(&key.clone()) {
                            *cnt_map.get(&key.clone()).unwrap() + cnt
                        } else {
                            cnt
                        },
                    );
                    for _ in 0..builder.len() {
                        builder.remove(0);
                    }
                } else {
                    for (key, _) in info.cnt_map.iter() {
                        cnt_map.insert(
                            key.clone(),
                            if cnt_map.contains_key(key) {
                                *cnt_map.get(key).unwrap()
                            } else {
                                0
                            } + *info.cnt_map.get(key).unwrap() * cnt,
                        );
                    }
                    info = Info::new(BTreeMap::new(), 0);
                }
                cnt = 0;
            }
            if s[i as usize] == '(' as u8 {
                info = process(s, i + 1);
                i = info.end + 1;
            } else {
                builder.push(s[i as usize] as char);
                i += 1;
            }
        } else if s[i as usize] >= 'a' as u8 && s[i as usize] <= 'z' as u8 {
            builder.push(s[i as usize] as char);
            i += 1;
        } else {
            cnt = cnt * 10 + s[i as usize] as i32 - '0' as i32;
            i += 1;
        }
    }
    if builder.len() != 0 || info.end != 0 {
        cnt = if cnt == 0 { 1 } else { cnt };
        if builder.len() != 0 {
            let key = builder.clone();
            cnt_map.insert(
                key.clone(),
                if cnt_map.contains_key(&key.clone()) {
                    *cnt_map.get(&key.clone()).unwrap() + cnt
                } else {
                    cnt
                },
            );
            for _ in 0..builder.len() {
                builder.remove(0);
            }
        } else {
            for (key, _) in info.cnt_map.iter() {
                cnt_map.insert(
                    key.clone(),
                    if cnt_map.contains_key(key) {
                        *cnt_map.get(key).unwrap()
                    } else {
                        0
                    } + *info.cnt_map.get(key).unwrap() * cnt,
                );
            }
        }
    }
    return Info::new(cnt_map, i);
}

执行结果如下：

左神java代码