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代码