https://www.cnblogs.com/grandyang/p/8667239.html
Given a chemical
formula (given as a string), return the count of each atom.
An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.
Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.
A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.
Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
Example 1:
Input:
formula = "H2O"
Output: "H2O"
Explanation:
The count of elements are {'H': 2, 'O': 1}.
Example 2:
Input:
formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation:
The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.
Example 3:
Input:
formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation:
The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
Note:
- All atom names consist of lowercase letters, except for the first character which is uppercase.
- The length of
formulawill be in the range[1, 1000]. formulawill only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.
X, Recursion
Write a function
parse that parses the formula from index i, returning a map count from names to multiplicities (the number of times that name is recorded).
We will put
i in global state: our parse function increments i throughout any future calls to parse.- When we see a
'(', we will parse whatever is inside the brackets (up to the closing ending bracket) and add it to our count. - Otherwise, we should see an uppercase character: we will parse the rest of the letters to get the name, and add that (plus the multiplicity if there is one.)
- At the end, if there is a final multiplicity (representing the multiplicity of a bracketed sequence), we'll multiply our answer by this.
- Time Complexity: , where is the length of the formula. It is to parse through the formula, but each of multiplicities after a bracket may increment the count of each name in the formula (inside those brackets), leading to an complexity.
- Space Complexity: . We aren't recording more intermediate information than what is contained in the formula.
int i; public String countOfAtoms(String formula) { StringBuilder ans = new StringBuilder(); i = 0; Map<String, Integer> count = parse(formula); for (String name: count.keySet()) { ans.append(name); int multiplicity = count.get(name); if (multiplicity > 1) ans.append("" + multiplicity); } return new String(ans); } public Map<String, Integer> parse(String formula) { int N = formula.length(); Map<String, Integer> count = new TreeMap(); while (i < N && formula.charAt(i) != ')') { if (formula.charAt(i) == '(') { i++; for (Map.Entry<String, Integer> entry: parse(formula).entrySet()) { count.put(entry.getKey(), count.getOrDefault(entry.getKey(), 0) + entry.getValue()); } } else { int iStart = i++; while (i < N && Character.isLowerCase(formula.charAt(i))) i++; String name = formula.substring(iStart, i); iStart = i; while (i < N && Character.isDigit(formula.charAt(i))) i++; int multiplicity = iStart < i ? Integer.parseInt(formula.substring(iStart, i)) : 1; count.put(name, count.getOrDefault(name, 0) + multiplicity); } } int iStart = ++i; while (i < N && Character.isDigit(formula.charAt(i))) i++; if (iStart < i) { int multiplicity = Integer.parseInt(formula.substring(iStart, i)); for (String key: count.keySet()) { count.put(key, count.get(key) * multiplicity); } } return count; }
private int i; public String countOfAtoms(String formula) { StringBuilder ans = new StringBuilder(); i = 0; Map<String, Integer> counts = countOfAtoms(formula.toCharArray()); for (String name: counts.keySet()) { ans.append(name); int count = counts.get(name); if (count > 1) ans.append("" + count); } return ans.toString(); } private Map<String, Integer> countOfAtoms(char[] f) { Map<String, Integer> ans = new TreeMap<String, Integer>(); while (i != f.length) { if (f[i] == '(') { ++i; Map<String, Integer> tmp = countOfAtoms(f); int count = getCount(f); for (Map.Entry<String, Integer> entry : tmp.entrySet()) ans.put(entry.getKey(), ans.getOrDefault(entry.getKey(), 0) + entry.getValue() * count); } else if (f[i] == ')') { ++i; return ans; } else { String name = getName(f); ans.put(name, ans.getOrDefault(name, 0) + getCount(f)); } } return ans; } private String getName(char[] f) { String name = "" + f[i++]; while (i < f.length && 'a' <= f[i] && f[i] <= 'z') name += f[i++]; return name; } private int getCount(char[] f) { int count = 0; while (i < f.length && '0' <= f[i] && f[i] <= '9') { count = count * 10 + (f[i] - '0'); ++i; } return count == 0 ? 1 : count; }
https://leetcode.com/problems/number-of-atoms/discuss/109346/Java-solution-Map-%2B-Recursion
X. Stack public String countOfAtoms(String formula) {
Map<String, Integer> map = countHelper(formula);
List<String> atoms = new ArrayList<>(map.keySet());
Collections.sort(atoms);
StringBuilder sb = new StringBuilder();
for (String atom : atoms) {
sb.append(atom + (map.get(atom) > 1 ? map.get(atom) : ""));
}
return sb.toString();
}
private Map<String, Integer> countHelper(String formula) {
Map<String, Integer> map = new HashMap<>();
if (formula.isEmpty()) return map;
int i = 0;
while (i < formula.length()) {
if (formula.charAt(i) == '(') {
int count = 0, j = i;
for (; j < formula.length(); j++) {
if (formula.charAt(j) == '(') count++;
else if (formula.charAt(j) == ')') count--;
if (count == 0) break;
}
Map<String, Integer> subMap = countHelper(formula.substring(i + 1, j));
j++;
int n = 1, k = j;
while (k < formula.length() && Character.isDigit(formula.charAt(k))) k++;
if (k > j) {
n = Integer.parseInt(formula.substring(j, k));
}
for (String atom : subMap.keySet()) {
map.put(atom, subMap.get(atom) * n + map.getOrDefault(atom, 0));
}
i = k;
} else {
int j = i + 1;
while (j < formula.length() && formula.charAt(j) >= 'a' && formula.charAt(j) <= 'z') j++;
int n = 1, k = j;
while (k < formula.length() && Character.isDigit(formula.charAt(k))) k++;
if (k > j) {
n = Integer.parseInt(formula.substring(j, k));
}
String atom = formula.substring(i, j);
map.put(atom, n + map.getOrDefault(atom, 0));
i = k;
}
}
return map;
}https://leetcode.com/problems/number-of-atoms/discuss/109345/Java-Solution-using-Stack-and-Map
public String countOfAtoms(String formula) { int N = formula.length(); Stack<Map<String, Integer>> stack = new Stack(); stack.push(new TreeMap()); for (int i = 0; i < N;) { if (formula.charAt(i) == '(') { stack.push(new TreeMap()); i++; } else if (formula.charAt(i) == ')') { Map<String, Integer> top = stack.pop(); int iStart = ++i, multiplicity = 1; while (i < N && Character.isDigit(formula.charAt(i))) i++; if (i > iStart) multiplicity = Integer.parseInt(formula.substring(iStart, i)); for (String c: top.keySet()) { int v = top.get(c); stack.peek().put(c, stack.peek().getOrDefault(c, 0) + v * multiplicity); } } else { int iStart = i++; while (i < N && Character.isLowerCase(formula.charAt(i))) i++; String name = formula.substring(iStart, i); iStart = i; while (i < N && Character.isDigit(formula.charAt(i))) i++; int multiplicity = i > iStart ? Integer.parseInt(formula.substring(iStart, i)) : 1; stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity); } } StringBuilder ans = new StringBuilder(); for (String name: stack.peek().keySet()) { ans.append(name); int multiplicity = stack.peek().get(name); if (multiplicity > 1) ans.append("" + multiplicity); } return new String(ans); }X. Regulare Expression
import java.util.regex.*; public String countOfAtoms(String formula) { Matcher matcher = Pattern.compile("([A-Z][a-z]*)(\\d*)|(\\()|(\\))(\\d*)").matcher(formula); Stack<Map<String, Integer>> stack = new Stack(); stack.push(new TreeMap()); while (matcher.find()) { String match = matcher.group(); if (match.equals("(")) { stack.push(new TreeMap()); } else if (match.startsWith(")")) { Map<String, Integer> top = stack.pop(); int multiplicity = match.length() > 1 ? Integer.parseInt(match.substring(1, match.length())) : 1; for (String name: top.keySet()) { stack.peek().put(name, stack.peek().getOrDefault(name, 0) + top.get(name) * multiplicity); } } else { int i = 1; while (i < match.length() && Character.isLowerCase(match.charAt(i))) { i++; } String name = match.substring(0, i); int multiplicity = i < match.length() ? Integer.parseInt(match.substring(i, match.length())) : 1; stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity); } } StringBuilder ans = new StringBuilder(); for (String name: stack.peek().keySet()) { ans.append(name); final int count = stack.peek().get(name); if (count > 1) ans.append(String.valueOf(count)); } return ans.toString(); }
这道题给了我们一个化学式，让我们数其中原子的个数。比如水是H2O，里面有两个氢原子，一个氧原子，返回还是H2O。例子2给的是氢氧化镁（哈哈，想不到这么多年过去了，高中化学还没有完全还给老师，呀，暴露年龄了呢|||-.-），里面有一个镁原子，氧原子和氢原子各两个，我们返回H2MgO2，可以看到元素是按字母顺序排列的，这道题就是纯粹玩字符串，不需要任何的化学知识。再看第三个例子K4(ON(SO3)2)2，就算你不认识里面的钾，硫，氮，氧等元素，也不影响做题，这个例子的返回是K4N2O14S4，钾原子有4个，氮原子有2个，氧原子有14个，是3x2x2 + 2 = 14得来的，硫原子有4个，是2x2 = 4得来的。那么我们可以发现规律，先统计括号里的原子个数，然后如果括号外面有数字，那么括号里每个原子的个数乘以外面的数字即可，然后在外层若还有数字，那么就继续乘这个数字，这种带有嵌套形式的字符串，比较适合用递归来做。我们最终的目的是统计每个原子的数量，所以我们只要建立了每个元素和其出现次数的映射，就可以生成返回的字符串了，由于需要按元素的字母顺序排列，所以我们使用TreeMap来建立映射。我们使用一个变量pos，来记录我们遍历的位置，这是个全局的变量，在递归函数参数中需要设置引用。我们遍历的时候，需要分三种情况讨论，分别是遇到左括号，右括号，和其他。我们一个个来看：
如果当前是左括号，那么我们pos先自增1，跳过括号位置，然后我们可以调用递归函数，来处理这个括号中包括的所有内容，外加上后面的数字，比如Mg(OH)2，在pos=2处遇到左括号，调用完递归函数后pos指向了最后一个字符的后一位，即pos=7。而在K4(ON(SO3)2)2中，如果是遇到中间的那个左括号pos=5时，调用完递归函数后pos指向了第二个右括号，即pos=11。递归函数返回了中间部分所有原子跟其个数之间的映射，我们直接将其都加入到当前的映射中即可。
如果当前是右括号，说明一个完整的括号已经遍历完了，我们需要取出其后面的数字，如果括号存在，那么后面一定会跟数字，否则不需要括号。所以我们先让pos自增1，跳过括号的位置，然后用个变量i记录当前位置，再进行while循环，找出第一个非数字的位置，那么中间就都是数字啦，用substr将其提取出来，并转为整数，然后遍历当前的映射对，每个值都乘以这个倍数即可，然后返回。
如果当前是字母，那么需要将元素名提取出来了，题目中说了元素名只有第一个字母是大写，后面如果有的话，都是小写字母。所以我们用个while循环找到第一个非小写字母的位置，用substr取出中间的字符串，即元素名。由于元素名后也可能跟数字，所以在用个while循环，来找之后第一个非数字的位置，用substr提取出数字字符串。当然也可能元素名后没有数字，提取出来的数字字符串就是空的，我们加的时候判断一下，如果为空就只加1，否则就加上转化后的整数
X. Videos
花花酱 LeetCode 726. Number of Atoms - 刷题找工作 EP108
