原子的数量(Leetcode 726)

发表于 | 分类于 ， ， | | 本文总阅读数 次
| 字数统计: 1.6k | 阅读时长 ≈ 7
Leetcode 726

1

题目分析

   本题虽然是一个困难题，但是思路却很清晰，难点主要在于代码量和对字符串的处理操作。这个题目有点类似于括号匹配和带有括号的计算问题，都是栈的经典解法，这给小伙伴们一些提示，能否使用栈的思想解决本题呢？

栈

对于化学表达式来说，括号外面的数字k表示括号里面的所有元素都有k个，若括号里面的某个元素有m个，则该元素有m x k个。所以类似于括号匹配问题，要一层一层将括号拆开。

但是本题的难点在于，元素和数字可能是多个字符，如Mg，20等，而且如果元素个数为1也会省略数字。所以字符串的处理会让本题的代码量变多。

为了便于处理，我们将本题可能出现的几种字符串类型进行区分
一个是数字类型，如20、4等
一个是元素类型，如N、Mg等
一个是括号类型，如(、)

用一个链表作为栈，其中元素为字符串

从第一个字符开始访问
如果当前字符是数字，则迭代去找后面的连续数字，然后判断前面是否有括号。如果有括号，则将括号内的元素全部取出，然后将括号去掉计算括号内外个数的乘积，如(O2)20，则先迭代找出20，然后将括号去掉，计算2x20=40，然后插入O40；如果没有括号直接将数字作为字符串插入如O20，则直接将20插入即可

如果当前字符是括号，直接将括号作为字符串入栈，然后判断该括号是否为右括号，如果是右括号，需要额外判断右括号的后面是否为数字，如果不是数字说明括号里面的内容只重复一次，如(H2)O2，右括号后面是O，等价于(H2)1O2，直接将括号去掉即可变为H2O2，如果后面是数字，则不用管它，在遍历到后面的数字时，会进行处理

如果当前字符是字母，则递归寻找后面的小写字母，不能寻找大写字母，因为这不是同一个元素，如MgO，找到Mg应该停止，说明是一个元素。此时也要进行额外判断，如果元素后面不是数字，则要加一个1，说明当前元素的个数为1。

一切都处理完后字符串中的所有括号都被去除，元素和个数成对出现，偶数下标为元素，奇数下标为对应的个数。如”K4(ON(SO3)2)2”，则会变为[“K”, “4”, “O”, “2”, “N”, “2”, “S”, “4”, “O”, “12”]，这时使用哈希表进行合并，因为同一个元素可能出现在多个地方，如O元素，而且根据TreeMap红黑树的底层实现，会自动进行排序，所以直接取出即可，否则还需要进行排序操作。

在取出的时候，也要判断，如果元素的个数为1，则不加入字符串中。

因为括号弹出可能会弹出栈中的所有元素，因此算法的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$

下面是Java语言的题解

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    public String countOfAtoms(String formula) {
        int length = formula.length();
        LinkedList<String> tmpStack = new LinkedList<>();
        LinkedList<String> stack = new LinkedList<>();
        TreeMap<String, Integer> map = new TreeMap<>();
        for (int i = 0; i < length;) {
            StringBuilder tmp = new StringBuilder();
            char cur = formula.charAt(i);
            if (cur >= '0' && cur <= '9') {
                while (cur >= '0' && cur <= '9') {
                    tmp.append(cur);
                    ++i;
                    if (i == length) { break; }
                    cur = formula.charAt(i);
                }
                if (stack.getLast().equals(")")) {
                    int num = Integer.parseInt(tmp.toString());
                    stack.removeLast();
                    while (!stack.getLast().equals("(")) {
                        tmpStack.add(stack.removeLast());
                    }
                    stack.removeLast();
                    while (!tmpStack.isEmpty()) {
                        stack.add(tmpStack.removeLast());
                        stack.add(Integer.toString(Integer.parseInt(tmpStack.removeLast()) * num));
                    }
                } else {
                    stack.add(tmp.toString());
                }
            } else if (cur == '(' || cur == ')') {
                tmp.append(cur);
                stack.add(tmp.toString());
                i++;
                if (cur == ')' && (i == length || (formula.charAt(i) < '0' || formula.charAt(i) > '9'))) {
                    stack.removeLast();
                    while (!stack.getLast().equals("(")) {
                        tmpStack.add(stack.removeLast());
                    }
                    stack.removeLast();
                    while (!tmpStack.isEmpty()) {
                        stack.add(tmpStack.removeLast());
                    }
                }
            } else {
                tmp.append(cur);
                if (i == length - 1) {
                    stack.add(tmp.toString());
                    stack.add("1");
                    break;
                }
                cur = formula.charAt(++i);
                while (cur >= 'a' && cur <= 'z') {
                    tmp.append(cur);
                    ++i;
                    if (i == length) { break; }
                    cur = formula.charAt(i);
                }
                stack.add(tmp.toString());
                if (cur < '0' || cur > '9') {
                    stack.add("1");
                }
            }
        }
        while (!stack.isEmpty()){
            String key = stack.removeFirst();
            int value = Integer.parseInt(stack.removeFirst());
            map.put(key, map.getOrDefault(key, 0) + value);
        }
        StringBuilder res = new StringBuilder();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            res.append(entry.getKey());
            if (entry.getValue() > 1) {
                res.append(entry.getValue());
            }
        }
        return res.toString();
    }
}

下面是Kotlin语言的题解

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
    fun countOfAtoms(formula: String): String {
        val stack = LinkedList<String>()
        val tmpStack = LinkedList<String>()
        val length = formula.length
        var idx = 0
        while (idx < length) {
            var cur = formula[idx]
            val tmp = StringBuilder()
            if (cur in '0'..'9') {
                while (cur in '0'..'9') {
                   tmp.append(cur)
                   ++idx
                   if (idx == length) { break }
                   cur = formula[idx]
                }
                if (stack.last() == ")") {
                    val num = tmp.toString().toInt()
                    stack.removeLast()
                    while (stack.last() != "(") {
                        tmpStack.add(stack.removeLast())
                    }
                    stack.removeLast()
                    while (tmpStack.isNotEmpty()) {
                        stack.add(tmpStack.removeLast())
                        stack.add((tmpStack.removeLast().toInt() * num).toString())
                    }
                } else {
                    stack.add(tmp.toString())
                }
            } else if (cur == '(' || cur == ')') {
                stack.add(cur.toString())
                ++idx
                if (cur == ')' && (idx == length || formula[idx] !in '0'..'9')) {
                    stack.removeLast()
                    while (stack.last() != "(") {
                        tmpStack.add(stack.removeLast())
                    }
                    stack.removeLast()
                    while (tmpStack.isNotEmpty()) {
                        stack.add(tmpStack.removeLast())
                    }
                }
            } else {
                tmp.append(cur)
                if (idx == length - 1) {
                    stack.add(tmp.toString())
                    stack.add("1")
                    break
                }
                cur = formula[++idx]
                while (cur in 'a'..'z') {
                    tmp.append(cur)
                    ++idx
                    if (idx == length) { break }
                    cur = formula[idx]
                }
                stack.add(tmp.toString())
                if (cur !in '0'..'9') {
                    stack.add("1")
                }
            }
        }
        val treeMap = TreeMap<String, Int>()
        while (stack.isNotEmpty()) {
            val key = stack.removeFirst()
            val value = treeMap.getOrDefault(key, 0) + stack.removeFirst().toInt()
            treeMap[key] = value
        }
        val res = StringBuilder()
        for (entry in treeMap) {
            res.append(entry.key)
            if (entry.value != 1) { res.append(entry.value) }
        }
        return res.toString()
    }
}

刷题总结

  本题的重点是括号匹配问题的扩展版本，能独立做出本题，这类问题都难不倒你。

-------------本文结束感谢您的阅读-------------
0%