726. Number of Atoms
LeetCode
hard
original: C#
#bit-manipulation
#csharp
#hard
#hash-table
#leetcode
#sort
#stack
#string
#tree
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Если задана строковая формула, представляющая химическую формулу, return количество атомов. Атомный element всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество elementов. НаEjemplo, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. НаEjemplo, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. НаEjemplo, "(H2O2)" и "(H2O2)3" являются формулами.
returns количество всех elementов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые Ejemploы генерируются таким образом, чтобы все значения в выводе помещались в 32-битное entero.
Ejemplo:
Input: formula = "H2O"
Output: "H2O"
C# solución
coincidente/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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.
После завершения обработки строки, объедините все словари из стека и отсортируйте результат.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.