LeetCode 726. 原子的数量

Categories:

题目描述
思路分析
1. 解法一：栈 + 解析（推荐）
相似题目

题目描述

✅ 726. 原子的数量

思路分析

解法一：栈 + 解析（推荐）

核心思路：

用栈保存当前层的原子计数表。

遇到 ( 入栈新表，遇到 ) 弹出并按倍数合并到上一层。

解析原子名与其后数字，更新当前表。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，栈与哈希表占用空间。

class Solution {
    public String countOfAtoms(String formula) {
        Deque<Map<String, Integer>> stack = new ArrayDeque<>();
        stack.push(new HashMap<>());

        int i = 0;
        int n = formula.length();

        while (i < n) {
            char c = formula.charAt(i);
            if (c == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (c == ')') {
                i++;
                int[] idx = new int[]{i};
                int mult = parseNum(formula, idx);
                i = idx[0];
                Map<String, Integer> top = stack.pop();
                Map<String, Integer> cur = stack.peek();
                for (Map.Entry<String, Integer> e : top.entrySet()) {
                    cur.put(e.getKey(), cur.getOrDefault(e.getKey(), 0) + e.getValue() * mult);
                }
            } else {
                StringBuilder name = new StringBuilder();
                name.append(c);
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    name.append(formula.charAt(i++));
                }

                int[] idx = new int[]{i};
                int mult = parseNum(formula, idx);
                i = idx[0];

                Map<String, Integer> cur = stack.peek();
                String atom = name.toString();
                cur.put(atom, cur.getOrDefault(atom, 0) + mult);
            }
        }

        Map<String, Integer> map = stack.pop();
        TreeMap<String, Integer> sorted = new TreeMap<>(map);
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> e : sorted.entrySet()) {
            sb.append(e.getKey());
            if (e.getValue() > 1) {
                sb.append(e.getValue());
            }
        }
        return sb.toString();
    }

    private int parseNum(String s, int[] idx) {
        int i = idx[0];
        int val = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            val = val * 10 + (s.charAt(i) - '0');
            i++;
        }
        idx[0] = i;
        return val == 0 ? 1 : val;
    }
}

func countOfAtoms(formula string) string {
	stack := make([]map[string]int, 0)
	stack = append(stack, make(map[string]int))

	i := 0
	n := len(formula)

	for i < n {
		c := formula[i]
		if c == '(' {
			stack = append(stack, make(map[string]int))
			i++
		} else if c == ')' {
			i++
			mult, next := parseNum(formula, i)
			i = next

			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			cur := stack[len(stack)-1]
			for k, v := range top {
				cur[k] += v * mult
			}
		} else {
			name := []byte{c}
			i++
			for i < n && formula[i] >= 'a' && formula[i] <= 'z' {
				name = append(name, formula[i])
				i++
			}

			mult, next := parseNum(formula, i)
			i = next

			atom := string(name)
			stack[len(stack)-1][atom] += mult
		}
	}

	mapCnt := stack[0]
	keys := make([]string, 0, len(mapCnt))
	for k := range mapCnt {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	var sb strings.Builder
	for _, k := range keys {
		sb.WriteString(k)
		if mapCnt[k] > 1 {
			sb.WriteString(strconv.Itoa(mapCnt[k]))
		}
	}
	return sb.String()
}

func parseNum(s string, i int) (int, int) {
	val := 0
	for i < len(s) && s[i] >= '0' && s[i] <= '9' {
		val = val*10 + int(s[i]-'0')
		i++
	}
	if val == 0 {
		return 1, i
	}
	return val, i
}

相似题目

题目	难度	考察点
394. 字符串解码	中等	栈
726. 原子的数量	困难	栈
856. 括号的分数	中等	栈
1106. 解析布尔表达式	困难	栈
20. 有效的括号	简单	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/13814431