题目描述
给你一个字符串化学式 formula ，返回 每种原子的数量 。
原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。
- 例如，
"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。
两个化学式连在一起可以构成新的化学式。
由括号括起的化学式并佐以数字（可选择性添加）也是化学式。
- 例如
"(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}。
提示：
1 <= formula.length <= 1000formula 由英文字母、数字、'(' 和 ')' 组成formula 总是有效的化学式
解法
方法一
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 | class Solution {
public String countOfAtoms(String formula) {
Map<String, Integer> map = new HashMap<>();
int[] stack = new int[1000];
int top = 0, multiplier = 1, freq = 0;
char[] c = formula.toCharArray();
for (int i = c.length - 1; i >= 0; i--) {
if (c[i] >= 'a' && c[i] <= 'z') {
int end = i--;
while (i >= 0 && c[i] >= 'a' && c[i] <= 'z') i--;
String key = new String(c, i, end - i + 1);
map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);
freq = 0;
} else if (c[i] >= 'A' && c[i] <= 'Z') {
String key = new String(c, i, 1);
map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);
freq = 0;
} else if (c[i] >= '0' && c[i] <= '9') {
freq = c[i] - '0';
int p = 10;
while (i - 1 >= 0 && c[i - 1] >= '0' && c[i - 1] <= '9') {
freq += p * (c[--i] - '0');
p *= 10;
}
} else if (c[i] == ')') {
stack[top++] = multiplier;
multiplier *= Math.max(freq, 1);
freq = 0;
} else {
multiplier = stack[--top];
}
}
List<String> keys = new ArrayList<>(map.keySet());
Collections.sort(keys);
StringBuilder sb = new StringBuilder();
for (String key : keys) {
sb.append(key);
int f = map.get(key);
if (f > 1) sb.append(f);
}
return sb.toString();
}
}
|
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 | function countOfAtoms(formula: string): string {
const getCount = (formula: string, factor = 1) => {
const n = formula.length;
const cnt: Record<string, number> = {};
const s: string[] = [];
let [atom, c] = ['', 0];
for (let i = 0; i <= n; i++) {
if (formula[i] === '(') {
const stk: string[] = ['('];
let j = i;
while (stk.length) {
j++;
if (formula[j] === '(') stk.push('(');
else if (formula[j] === ')') stk.pop();
}
const molecule = formula.slice(i + 1, j);
const nextFactor: string[] = [];
while (isDigit(formula[++j])) {
nextFactor.push(formula[j]);
}
const nextC = getCount(molecule, +nextFactor.join('') || 1);
for (const [atom, c] of Object.entries(nextC)) {
cnt[atom] = (cnt[atom] ?? 0) + c * factor;
}
i = j - 1;
continue;
}
if (s.length && (!formula[i] || isUpper(formula[i]))) {
[atom, c] = getAtom(s);
c *= factor;
cnt[atom] = (cnt[atom] ?? 0) + c;
s.length = 0;
}
s.push(formula[i]);
}
return cnt;
};
return Object.entries(getCount(formula))
.sort(([a], [b]) => a.localeCompare(b))
.map(([a, b]) => (b > 1 ? a + b : a))
.join('');
}
const regex = {
atom: /(\D+)(\d+)?/,
isUpper: /[A-Z]+/,
};
const getAtom = (s: string[]): [string, number] => {
const [_, atom, c] = regex.atom.exec(s.join(''))!;
return [atom, c ? +c : 1];
};
const isDigit = (ch: string) => !Number.isNaN(Number.parseInt(ch));
const isUpper = (ch: string) => regex.isUpper.test(ch);
|
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 | /**
* @param {string} formula
* @return {string}
*/
var countOfAtoms = function (formula) {
const getCount = (formula, factor = 1) => {
const n = formula.length;
const cnt = {};
const s = [];
let [atom, c] = ['', 0];
for (let i = 0; i <= n; i++) {
if (formula[i] === '(') {
const stk = ['('];
let j = i;
while (stk.length) {
j++;
if (formula[j] === '(') stk.push('(');
else if (formula[j] === ')') stk.pop();
}
const molecule = formula.slice(i + 1, j);
const nextFactor = [];
while (isDigit(formula[++j])) {
nextFactor.push(formula[j]);
}
const nextC = getCount(molecule, +nextFactor.join('') || 1);
for (const [atom, c] of Object.entries(nextC)) {
cnt[atom] = (cnt[atom] ?? 0) + c * factor;
}
i = j - 1;
continue;
}
if (s.length && (!formula[i] || isUpper(formula[i]))) {
[atom, c] = getAtom(s);
c *= factor;
cnt[atom] = (cnt[atom] ?? 0) + c;
s.length = 0;
}
s.push(formula[i]);
}
return cnt;
};
return Object.entries(getCount(formula))
.sort(([a], [b]) => a.localeCompare(b))
.map(([a, b]) => (b > 1 ? a + b : a))
.join('');
};
const regex = {
atom: /(\D+)(\d+)?/,
isUpper: /[A-Z]+/,
};
const getAtom = s => {
const [_, atom, c] = regex.atom.exec(s.join(''));
return [atom, c ? +c : 1];
};
const isDigit = ch => !Number.isNaN(Number.parseInt(ch));
const isUpper = ch => regex.isUpper.test(ch);
|