列表

详情

726. 原子的数量

给你一个字符串化学式 formula ，返回 每种原子的数量 。

原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。

两个化学式连在一起可以构成新的化学式。

由括号括起的化学式并佐以数字（可选择性添加）也是化学式。

返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 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}。

 

提示：

相似题目

字符串解码

编码最短长度的字符串

Lisp 语法解析

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: string countOfAtoms(string formula) { } };

python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-05-24 17:47:22 

'''
左右括号内的乘的基数可以从后面先累加，
遇到左括号除以上一个乘数得到后面(倒序的后面就是正序的前面)的基数即可
'''
class Solution:
    def countOfAtoms(self, formula: str) -> str:
        # 倒着的时候， 记录map，乘的基数，迭代中的乘数，个数，个数的10进制位数，元素
        cnts, multiply, muls, num, num_count, atom = defaultdict(int), 1, [], 0, 0, ""
        for c in formula[::-1]:
            if c == ')':
                # 如果当前有统计的数字，乘的基数要叠加
                if num:
                    multiply *= num
                    muls.append(num)
                    num = num_count = 0
                else:
                    muls.append(1)
            elif c == '(':
                # 去除掉上一个乘数
                multiply //= muls.pop()
            elif str.isdigit(c):
                num += int(c) * (10 ** num_count)
                num_count += 1
            elif str.islower(c):
                atom += c
            else:
                atom += c
                # 注意我们在更新元素个数时，始终要考虑乘的基数
                if num:
                    cnts[atom[::-1]] += num * multiply
                else:
                    cnts[atom[::-1]] += multiply
                atom = ""
                num = num_count = 0
        return "".join(key if cnts[key] == 1 else key + str(cnts[key]) for key in sorted(cnts.keys()))

javascript 解法, 执行用时: 92 ms, 内存消耗: 46.8 MB, 提交时间: 2023-05-24 17:46:41 

/**
 * @param {string} formula
 * @return {string}
 */
var countOfAtoms = function(formula) {
    let i = 0;
    const n = formula.length;

    const stack = [new Map()];
    while (i < n) {
        const ch = formula[i];

        const parseAtom = () => {
            const sb = [];
            sb.push(formula[i++]); // 扫描首字母
            while (i < n && formula[i] >= 'a' && formula[i] <= 'z') {
                sb.push(formula[i++]); // 扫描首字母后的小写字母
            }
            return sb.join('');
        }

        const parseNum = () => {
            if (i === n || isNaN(Number(formula[i]))) {
                return 1; // 不是数字，视作 1
            }
            let num = 0;
            while (i < n && !isNaN(Number(formula[i]))) {
                num = num * 10 + formula[i++].charCodeAt() - '0'.charCodeAt(); // 扫描数字
            }
            return num;
        }

        if (ch === '(') {
            i++;
            stack.unshift(new Map()); // 将一个空的哈希表压入栈中，准备统计括号内的原子数量
        } else if (ch === ')') {
            i++;
            const num = parseNum(); // 括号右侧数字
            const popMap = stack.shift(); // 弹出括号内的原子数量
            const topMap = stack[0];
            for (const [atom, v] of popMap.entries()) {
                topMap.set(atom, (topMap.get(atom) || 0) + v * num); // 将括号内的原子数量乘上 num，加到上一层的原子数量中
            }
        } else {
            const atom = parseAtom();
            const num = parseNum();
            const topMap = stack[0];
            topMap.set(atom, (topMap.get(atom) || 0) + num); // 统计原子数量
            
        }
    }

    let map = stack.pop();
    map = Array.from(map);
    map.sort();
    const sb = [];
    for (const [atom, count] of map) {
        sb.push(atom);
        if (count > 1) {
            sb.push(count);
        }
    }
    return sb.join('');
};

java 解法, 执行用时: 3 ms, 内存消耗: 39.7 MB, 提交时间: 2023-05-24 17:46:27 

class Solution {
    int i, n;
    String formula;

    public String countOfAtoms(String formula) {
        this.i = 0;
        this.n = formula.length();
        this.formula = formula;

        Deque<Map<String, Integer>> stack = new LinkedList<Map<String, Integer>>();
        stack.push(new HashMap<String, Integer>());
        while (i < n) {
            char ch = formula.charAt(i);
            if (ch == '(') {
                i++;
                stack.push(new HashMap<String, Integer>()); // 将一个空的哈希表压入栈中，准备统计括号内的原子数量
            } else if (ch == ')') {
                i++;
                int num = parseNum(); // 括号右侧数字
                Map<String, Integer> popMap = stack.pop(); // 弹出括号内的原子数量
                Map<String, Integer> topMap = stack.peek();
                for (Map.Entry<String, Integer> entry : popMap.entrySet()) {
                    String atom = entry.getKey();
                    int v = entry.getValue();
                    topMap.put(atom, topMap.getOrDefault(atom, 0) + v * num); // 将括号内的原子数量乘上 num，加到上一层的原子数量中
                }
            } else {
                String atom = parseAtom();
                int num = parseNum();
                Map<String, Integer> topMap = stack.peek();
                topMap.put(atom, topMap.getOrDefault(atom, 0) + num); // 统计原子数量
            }
        }

        Map<String, Integer> map = stack.pop();
        TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>(map);

        StringBuffer sb = new StringBuffer();
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            String atom = entry.getKey();
            int count = entry.getValue();
            sb.append(atom);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }

    public String parseAtom() {
        StringBuffer sb = new StringBuffer();
        sb.append(formula.charAt(i++)); // 扫描首字母
        while (i < n && Character.isLowerCase(formula.charAt(i))) {
            sb.append(formula.charAt(i++)); // 扫描首字母后的小写字母
        }
        return sb.toString();
    }

    public int parseNum() {
        if (i == n || !Character.isDigit(formula.charAt(i))) {
            return 1; // 不是数字，视作 1
        }
        int num = 0;
        while (i < n && Character.isDigit(formula.charAt(i))) {
            num = num * 10 + formula.charAt(i++) - '0'; // 扫描数字
        }
        return num;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-05-24 17:46:08 

func countOfAtoms(formula string) string {
    i, n := 0, len(formula)

    parseAtom := func() string {
        start := i
        i++ // 扫描，跳过首字母
        for i < n && unicode.IsLower(rune(formula[i])) { 
            i++ // 扫描首字母后的小写字母
        }
        return formula[start:i]
    }

    parseNum := func() (num int) {
        if i == n || !unicode.IsDigit(rune(formula[i])) { 
            return 1 // 不是数字，视作 1
        }
        for ; i < n && unicode.IsDigit(rune(formula[i])); i++ { 
            num = num*10 + int(formula[i]-'0') // 扫描数字
        }
        return
    }

    stk := []map[string]int{{}}
    for i < n {
        if ch := formula[i]; ch == '(' {
            i++
            stk = append(stk, map[string]int{}) // 将一个空的哈希表压入栈中，准备统计括号内的原子数量
        } else if ch == ')' {
            i++
            num := parseNum() // 括号右侧数字
            atomNum := stk[len(stk)-1]
            stk = stk[:len(stk)-1] // 弹出括号内的原子数量
            for atom, v := range atomNum {
                stk[len(stk)-1][atom] += v * num // 将括号内的原子数量乘上 num，加到上一层的原子数量中
            }
        } else {
            atom := parseAtom()
            num := parseNum()
            stk[len(stk)-1][atom] += num // 统计原子数量
        }
    }

    atomNum := stk[0]
    type pair struct {
        atom string
        num  int
    }
    pairs := make([]pair, 0, len(atomNum))
    for k, v := range atomNum {
        pairs = append(pairs, pair{k, v})
    }
    sort.Slice(pairs, func(i, j int) bool { return pairs[i].atom < pairs[j].atom })

    ans := []byte{}
    for _, p := range pairs {
        ans = append(ans, p.atom...)
        if p.num > 1 {
            ans = append(ans, strconv.Itoa(p.num)...)
        }
    }
    return string(ans)
}

上一题

© 2025 leetcode.cn