VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 726. 原子的数量

Posted on Edited on In , ,

摘要：
很容易想到使用DFS解决问题。

题目

给定一个化学式 $formula$（作为字符串），返回每种原子的数量。

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

如果数量大于 $1$，原子后会跟着数字表示原子的数量。如果数量等于 $1$ 则不会跟数字。例如，$H2O$ 和 $H2O2$ 是可行的，但 $H1O2$ 这个表达是不可行的。

两个化学式连在一起是新的化学式。例如 $H2O2He3Mg4$ 也是化学式。

一个括号中的化学式和数字（可选择性添加）也是化学式。例如 $(H2O2)$ 和 $(H2O2)3$ 是化学式。

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

示例 4：

输入：formula = “Be32”
输出：”Be32”

提示：

  • $1 <= formula.length <= 1000$
  • $formula$ 由小写英文字母、数字 ( 和 ) 组成。
  • $formula$ 是有效的化学式。

DFS

本题会遇到嵌套的括号，可以使用递归解决问题。
每遇到左括号就进入递归，并计算括号内的原子数量，保存在 map 中。
遇到右括号递归终止，返回。
回溯阶段判断右括号外的倍数问题，将返回的 map 中原子数目全部乘倍数。
因为题目要求使用字典序输出内容，故不使用 unordered_map 而使用 map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
 * 2021-7-6 00:43:56
 * author: etoa
 */
class Solution {
public:
    int n;
    string countOfAtoms(string formula) {
        n = formula.size();
        int u = 0;
        auto ordereded_map = dfs(formula, u);
        
        string res;
        for (auto &[atom, cnt] : ordereded_map) {
            res += atom;
            if (cnt > 1) res += to_string(cnt);
        }
        return res;
    }

    map<string, int> dfs(string &formula, int &u) {
        map<string, int> tres;
        for (; u < n;) {
            if (formula[u] == '(') {
                ++u;
                auto tmap = dfs(formula, u);
                // checks if current is digits
                int mul = 0, k = u;
                for (; k < n && isdigit(formula[k]); ++k) {
                    mul = mul * 10 + formula[k] - '0';
                }
                if (!mul) ++mul;
                u = k;
                // merge
                for (auto &[atom, cnt] : tmap) {
                    tres[atom] += cnt * mul;
                }
            }
            else if (formula[u] == ')') {    // endof dfs
                ++u;
                break;
            }
            else { 
                int k = u + 1;  // 从字母的下一位开始
                string atom;
                for (; k < n && islower(formula[k]); ++k);
                int atomlen = k - u;
                atom = formula.substr(u, atomlen);
                //cout << atom << endl;
                
                int cnt = 0;
                for (; k < n && isdigit(formula[k]); k++) {
                    cnt = cnt * 10 + formula[k] - '0';
                }
                if (!cnt) ++cnt;
                //cout << cnt << endl;
                tres[atom] += cnt;
                u = k;
            }
        }
        return tres;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * author: yxc@acwing
 */
typedef map<string, int> MPSI;

class Solution {
public:
    MPSI dfs(string& str, int& u) {
        MPSI res;
        while (u < str.size()) {
            if (str[u] == '(') {
                u ++ ;
                auto t = dfs(str, u);
                u ++ ;
                int cnt = 1, k = u;
                while (k < str.size() && isdigit(str[k])) k ++ ;
                if (k > u) {
                    cnt = stoi(str.substr(u, k - u));
                    u = k;
                }
                for (auto& [x, y]: t) res[x] += y * cnt;
            } else if (str[u] == ')') break;
            else {
                int k = u + 1;
                while (k < str.size() && str[k] >= 'a' && str[k] <= 'z') k ++ ;
                auto key = str.substr(u, k - u);
                u = k;
                int cnt = 1;
                while (k < str.size() && isdigit(str[k])) k ++ ;
                if (k > u) {
                    cnt = stoi(str.substr(u, k - u));
                    u = k;
                }
                res[key] += cnt;
            }
        }
        return res;
    }

    string countOfAtoms(string formula) {
        int k = 0;
        auto t = dfs(formula, k);
        string res;
        for (auto& [x, y]: t) {
            res += x;
            if (y > 1) res += to_string(y);
        }
        return res;
    }
};

原题链接： LeetCode 726. 原子的数量