726. Number of Atoms
LeetCode
hard
original: C#
#bit-manipulation
#csharp
#hard
#hash-table
#leetcode
#sort
#stack
#string
#tree
Task text is translated from Russian for the selected interface language. Code is left unchanged.
Если задана строковая формула, представляющая химическую формулу, return количество атомов. Атомный element всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество elementов. НаExample, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. НаExample, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. НаExample, "(H2O2)" и "(H2O2)3" являются формулами.
returns количество всех elementов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые Exampleы генерируются таким образом, чтобы все значения в выводе помещались в 32-битное integer.
Example:
Input: formula = "H2O"
Output: "H2O"
C# solution
matched/originalpublic class Solution {
public string CountOfAtoms(string formula) {
var stack = new Stack<Dictionary<string, int>>();
stack.Push(new Dictionary<string, int>());
int n = formula.Length;
int i = 0;
while (i < n) {
if (formula[i] == '(') {
stack.Push(new Dictionary<string, int>());
i++;
} else if (formula[i] == ')') {
var top = stack.Pop();
i++;
int start = i;
while (i < n && Char.IsDigit(formula[i])) {
i++;
}
int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
foreach (var name in top.Keys) {
int count = top[name];
if (stack.Peek().ContainsKey(name)) {
stack.Peek()[name] += count * multiplicity;
} else {
stack.Peek()[name] = count * multiplicity;
}
}
} else {
int start = i;
i++;
while (i < n && Char.IsLower(formula[i])) {
i++;
}
string name = formula.Substring(start, i - start);
start = i;
while (i < n && Char.IsDigit(formula[i])) {
i++;
}
int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
if (stack.Peek().ContainsKey(name)) {
stack.Peek()[name] += multiplicity;
} else {
stack.Peek()[name] = multiplicity;
}
}
}
var countMap = stack.Pop();
var sb = new StringBuilder();
foreach (var name in countMap.Keys.OrderBy(x => x)) {
sb.Append(name);
int count = countMap[name];
if (count > 1) {
sb.Append(count);
}
}
return sb.ToString();
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public string CountOfAtoms(string formula) {
var stack = new stack<unordered_map<string, int>>();
stack.push(new unordered_map<string, int>());
int n = formula.size();
int i = 0;
while (i < n) {
if (formula[i] == '(') {
stack.push(new unordered_map<string, int>());
i++;
} else if (formula[i] == ')') {
var top = stack.pop();
i++;
int start = i;
while (i < n && Char.IsDigit(formula[i])) {
i++;
}
int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
foreach (var name in top.Keys) {
int count = top[name];
if (stack.Peek().count(name)) {
stack.Peek()[name] += count * multiplicity;
} else {
stack.Peek()[name] = count * multiplicity;
}
}
} else {
int start = i;
i++;
while (i < n && Char.IsLower(formula[i])) {
i++;
}
string name = formula.Substring(start, i - start);
start = i;
while (i < n && Char.IsDigit(formula[i])) {
i++;
}
int multiplicity = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
if (stack.Peek().count(name)) {
stack.Peek()[name] += multiplicity;
} else {
stack.Peek()[name] = multiplicity;
}
}
}
var countMap = stack.pop();
var sb = new StringBuilder();
foreach (var name in countMap.Keys.OrderBy(x => x)) {
sb.Append(name);
int count = countMap[name];
if (count > 1) {
sb.Append(count);
}
}
return sb.ToString();
}
}Java solution
matched/originalimport java.util.*;
public class Solution {
public String countOfAtoms(String formula) {
Stack<Map<String, Integer>> stack = new Stack<>();
stack.push(new HashMap<>());
int n = formula.length();
int i = 0;
while (i < n) {
if (formula.charAt(i) == '(') {
stack.push(new HashMap<>());
i++;
} else if (formula.charAt(i) == ')') {
Map<String, Integer> top = stack.pop();
i++;
int start = i;
while (i < n && Character.isDigit(formula.charAt(i))) {
i++;
}
int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
for (String name : top.keySet()) {
int count = top.get(name);
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count * multiplicity);
}
} else {
int start = i;
i++;
while (i < n && Character.isLowerCase(formula.charAt(i))) {
i++;
}
String name = formula.substring(start, i);
start = i;
while (i < n && Character.isDigit(formula.charAt(i))) {
i++;
}
int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
}
}
Map<String, Integer> countMap = stack.pop();
StringBuilder sb = new StringBuilder();
for (String name : new TreeMap<>(countMap).keySet()) {
sb.append(name);
int count = countMap.get(name);
if (count > 1) {
sb.append(count);
}
}
return sb.toString();
}
}JavaScript solution
matched/originalvar countOfAtoms = function(formula) {
const stack = [new Map()];
let i = 0, n = formula.length;
while (i < n) {
if (formula[i] === '(') {
stack.push(new Map());
i++;
} else if (formula[i] === ')') {
const top = stack.pop();
i++;
let multiplicity = 0;
while (i < n && !isNaN(formula[i])) {
multiplicity = multiplicity * 10 + parseInt(formula[i]);
i++;
}
multiplicity = multiplicity || 1;
for (const [name, count] of top) {
stack[stack.length - 1].set(name, (stack[stack.length - 1].get(name) || 0) + count * multiplicity);
}
} else {
let start = i;
i++;
while (i < n && formula[i] >= 'a' && formula[i] <= 'z') {
i++;
}
const name = formula.slice(start, i);
let multiplicity = 0;
while (i < n && !isNaN(formula[i])) {
multiplicity = multiplicity * 10 + parseInt(formula[i]);
i++;
}
multiplicity = multiplicity || 1;
stack[stack.length - 1].set(name, (stack[stack.length - 1].get(name) || 0) + multiplicity);
}
}
const countMap = stack.pop();
return Array.from(countMap).sort().map(([name, count]) => name + (count > 1 ? count : '')).join('');
};Python solution
matched/originalimport collections
def countOfAtoms(formula: str) -> str:
stack = [collections.Counter()]
i, n = 0
while i < n:
if formula[i] == '(':
stack.append(collections.Counter())
i += 1
elif formula[i] == ')':
top = stack.pop()
i += 1
i_start = i
while i < n and formula[i].isdigit():
i += 1
multiplicity = int(formula[i_start:i] or 1)
for name, count in top.items():
stack[-1][name] += count * multiplicity
else:
i_start = i
i += 1
while i < n and formula[i].islower():
i += 1
name = formula[i_start:i]
i_start = i
while i < n and formula[i].isdigit():
i += 1
multiplicity = int(formula[i_start:i] or 1)
stack[-1][name] += multiplicity
result = ''
for name in sorted(stack[-1]):
result += name
if stack[-1][name] > 1:
result += str(stack[-1][name])
return resultGo solution
matched/originalpackage main
import (
"fmt"
"sort"
"strconv"
"unicode"
)
func countOfAtoms(formula string) string {
stack := []map[string]int{{}}
n := len(formula)
i := 0
for i < n {
if formula[i] == '(' {
stack = append(stack, map[string]int{})
i++
} else if formula[i] == ')' {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
i++
iStart := i
for i < n && unicode.IsDigit(rune(formula[i])) {
i++
}
multiplicity, _ := strconv.Atoi(formula[iStart:i])
if multiplicity == 0 {
multiplicity = 1
}
for name, count := range top {
stack[len(stack)-1][name] += count * multiplicity
}
} else {
iStart := i
i++
for i < n && unicode.IsLower(rune(formula[i])) {
i++
}
name := formula[iStart:i]
iStart = i
for i < n && unicode.IsDigit(rune(formula[i])) {
i++
}
multiplicity, _ := strconv.Atoi(formula[iStart:i])
if multiplicity == 0 {
multiplicity = 1
}
stack[len(stack)-1][name] += multiplicity
}
}
countMap := stack[0]
keys := make([]string, 0, len(countMap))
for key := range countMap {
keys = append(keys, key)
}
sort.Strings(keys)
result := ""
for _, name := range keys {
result += name
if countMap[name] > 1 {
result += strconv.Itoa(countMap[name])
}
}
return result
}Algorithm
Используйте стек для отслеживания текущего уровня скобок.
Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее number, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.
После завершения обработки строки, объедините все словари из стека и отсортируйте результат.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.